序論：好文章的創(chuàng)作是一個(gè)不斷探索和完善的過(guò)程，我們?yōu)槟扑]十篇匹配算法論文范例，希望它們能助您一臂之力，提升您的閱讀品質(zhì)，帶來(lái)更深刻的閱讀感受。

篇（1）

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)生歧義，這種歧義稱為組合歧義。為了減少這種歧義的影響，本系統(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）

[4]

ZAKI T， ESSAADY Y， MAMMASS D， et al. A hybrid method ngramsTFIDF with radial basis for indexing and classification of Arabic document [J]. International Journal of Software Engineering and Its Applications， 2014， 8（2）： 127-144.

[5]

SIDOROV G， VELASQUEZ F， STAMATATOS E， et al. Syntactic dependencybased ngrams as classification features [C]// MICAI 2012： Proceedings of the 11th Mexican International Conference on Artificial Intelligence， LNCS 7630. Berlin： Springer， 2013： 1-11.

[6]

YI Y， GUAN J， ZHOU S. Effective clustering of microRNA sequences by ngrams and feature weighting [C] // Proceedings of the 2012 IEEE 6th International Conference on Systems Biology. Piscataway： IEEE， 2012： 203-210.

[7]

BOURAS C， TSOGKAS V. Enhancing news articles clustering using word ngrams [C] // DATA 2013： Proceedings of the 2nd International Conference on Data Technologies and Applications. London： dblp Computer Science Bibliography， 2013： 53-60.

[8]

GHANNAY S， BARRAULT L. Using hypothesis selection based features for confusion network MT system combination [C] // EACL 2014： Proceedings of the 3rd Workshop on Hybrid Approaches to Translation （HyTra）. Stroudsburg： Association for Computational Linguistics， 2014： 2-6.

[9]

SIDOROV G， VELASQUEZ F， STAMATAOS E， et al. Syntactic ngrams as machine learning features for natural language processing [J]. Expert Systems with Applications， 2014， 41（3）： 853-860.

[10]

HAN Q， GUO J， SCHTZE H. CodeX： combining an SVM classifier and character ngram language models for sentiment analysis on Twitter text [C]// SemEval 2013： Proceedings of the Second Joint Conference on Lexical and Computational Semantics （*SEM）， Volume 2： Proceedings of the Seventh International Workshop on Semantic Evaluation. Stroudsburg： Association for Computational Linguistics， 2013： 520-524.

http：//p.nus.edu.sg/～antho/S/S13/S13-2086.pdf

[11]

BESPALOY D， BAI B， QI Y， et al. Sentiment classification based on supervised latent ngram analysis [C] // CIKM 11： Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 375-382.

[12]

MILLER Z， DICKINSON B， HU W. Gender prediction on Twitter using stream algorithms with ngram character features [J]. International Journal of Intelligence Science， 2012， 2（4A）： 143-148.

[13]

WRIGHT J， LLOYDTHOMAS H. A robust language model incorporating a substring parser and extended ngrams [C] // ICASSP 1994： Proceedings of the 1994 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 1994： 361-364.

[14]

HACIOGLU K， WARD W. Dialogcontext dependent language modeling combining ngrams and stochastic contextfree grammars [C] // ICASSP 2001： Proceedings of the 2001 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 2001， 1： 537-540.

[15]

SIU M， OSTENDORF M. Variable ngrams and extensions for conversational speech language modeling [J]. Speech and Audio Processing， 2000， 1（8）： 63-75.

[16]

ZHOU S， GUAN J， HU Y， et al. A Chinese document categorization system without dictionary support and segmentation processing [J]. Journal of Computer Research and Development， 2001， 38（7）： 839-844. （周水庚，關(guān)佶紅，胡運(yùn)發(fā)，等.一個(gè)無(wú)需詞典支持和切詞處理的中文文檔分類(lèi)系統(tǒng)[J].計(jì)算機(jī)研究與發(fā)展，2001，38（7）：839-844）

[17]

GAO Z， LI X. Feature extraction method based on sliding window application in text classification[J]. Science & Technology Information， 2008（34）： 23-24. （高振峰，李錫祚.基于滑動(dòng)窗口的特征提取方法在文本分類(lèi)中的應(yīng)用[J].科技信息：學(xué)術(shù)版，2008（34）：23-24.）

[18]

篇（3）

中圖分類(lèi)號(hào)：TP311.52

1 引言

在現(xiàn)有的畢業(yè)論文選題系統(tǒng)中，一個(gè)學(xué)生只能選擇一個(gè)題目作為自己最終的題目，同樣，一個(gè)題目只能分配給一個(gè)學(xué)生。如果最后題目由學(xué)生自己確定，那就會(huì)出現(xiàn)先選的學(xué)生具有更大的選擇余地，后選的學(xué)生由于不能再選已經(jīng)選定的題目，所以其可選擇的題目會(huì)越來(lái)越少，這對(duì)很多學(xué)生來(lái)說(shuō)很不公平。如果學(xué)生選擇自己的志愿，最終題目由老師來(lái)定，這不但加大了老師的工作量，而且還是不能保證每位同學(xué)的公平性。如何采用計(jì)算機(jī)智能輔助選題，設(shè)計(jì)最優(yōu)匹配算法實(shí)現(xiàn)學(xué)生與題目的整體最優(yōu)匹配，會(huì)大大提高選題的效率。

湯穎曾在《畢業(yè)設(shè)計(jì)立項(xiàng)與選題管理及其支持系統(tǒng)》中提出，采用模糊匹配技術(shù)進(jìn)行學(xué)生-題目的自動(dòng)匹配；潘志方在《一種改進(jìn)的Ford-Fulkenson算法在選題系統(tǒng)中的應(yīng)用研究》中將題目與學(xué)生的匹配抽象為二分圖的匹配，并采用改進(jìn)的Ford-Fulkenson算法實(shí)現(xiàn)題目與學(xué)生的自動(dòng)匹配。以上兩種方法只考慮了學(xué)生與題目之間的最大匹配值，并沒(méi)有考慮學(xué)生的整體滿意度最優(yōu)的情況。

本文將通過(guò)采用最優(yōu)匹配算法（KM）確定一種匹配方案，使得學(xué)生的整體滿意度最高。具體方法概括如下：學(xué)生預(yù)選多個(gè)題目，并根據(jù)自己對(duì)題目的滿意度由高到底排序，這樣，滿意度成為二分圖的一分值，如圖1所示：

2 系統(tǒng)功能模塊設(shè)計(jì)

根據(jù)前期的可行性分析，本系統(tǒng)主要進(jìn)行以下模塊的設(shè)計(jì)：系統(tǒng)管理員模塊、專業(yè)負(fù)責(zé)人管理模塊、指導(dǎo)教師管理模塊和學(xué)生選題模塊。

系統(tǒng)管理員模塊主要負(fù)責(zé)對(duì)系統(tǒng)參數(shù)的設(shè)置及用戶的管理。主要實(shí)現(xiàn)以下功能：

（1）系統(tǒng)設(shè)置：對(duì)系統(tǒng)標(biāo)題、畢業(yè)生、選題參數(shù)設(shè)置；

（2）學(xué)院及專業(yè)設(shè)置：完成學(xué)院、專業(yè)的添加、刪除、修改操作；

（3）數(shù)據(jù)字典的維護(hù)：教師信息、選題難度、選題方向燈信息的維護(hù)；

（4）教師和學(xué)生的管理：完成教師、學(xué)生信息的添加、刪除和修改操作；

（5）文件文化建設(shè)管理：日志文件查看、上傳文件的管理。

專業(yè)負(fù)責(zé)人管理模塊與系統(tǒng)管理員權(quán)限相似，但操作的數(shù)據(jù)只能針對(duì)于指定專業(yè)，無(wú)法瀏覽及操作整個(gè)學(xué)院的課題及學(xué)生信息。最重要的功能是實(shí)現(xiàn)題目的審核。

導(dǎo)師管理模塊主要用于選題以及選擇自己選題學(xué)生的審核確認(rèn)。

（1）個(gè)人中心管理：如信息修改及密碼重置；

（2）選題管理：選題的增加、修改、刪除以及選題類(lèi)型的設(shè)置；

（3）學(xué)生選題查詢及審核。

學(xué)生模塊主要實(shí)現(xiàn)學(xué)生選題的選擇及確認(rèn)。

（1）學(xué)生個(gè)人信息的修改；

（2）學(xué)生選題及確認(rèn)信息查詢；

（3）學(xué)生留言及咨詢。

3 KM算法在系統(tǒng)中的實(shí)現(xiàn)

KM算法由Kuhn和Munkras分別提出來(lái)，這是一種問(wèn)題。經(jīng)典的算法。該算法由通過(guò)每個(gè)頂點(diǎn)一個(gè)頂標(biāo)（A[i][j]）來(lái)求最大權(quán)匹配的問(wèn)題轉(zhuǎn)化為不斷尋找增廣道路以使二分圖的匹配數(shù)達(dá)到最大的完備匹配。KM算法的關(guān)鍵在于不斷尋找二分圖中的可增廣道路。如果找到一條可增廣道路，就可以額將屬于和不屬于相等子圖的邊取相反，從而相等子圖里就是增加一條邊，一直到所有的頂點(diǎn)都進(jìn)入相等子圖為止。

KM算法可以很好地解決選題系統(tǒng)中，題目與學(xué)生最優(yōu)匹配的問(wèn)題。下面以國(guó)際商學(xué)院09級(jí)本科學(xué)生選題為例。

在匹配過(guò)程中，設(shè)學(xué)生的集合為X={X1，X2，X3……Xn}，選題的集合設(shè)置為Y={Y1，Y2，Y3……Yn}，學(xué)生對(duì)自己選題的滿意度為二維矩陣Z[m][n]，其他題目規(guī)定權(quán)值為0。系統(tǒng)規(guī)定學(xué)生最多可預(yù)選3個(gè)題目，并按照滿意度分別設(shè)置0.9，0.7，0.5。以下表1是對(duì)國(guó)際經(jīng)濟(jì)與貿(mào)易專業(yè)使用不同算法得出的學(xué)生滿意程度。

下面對(duì)以上數(shù)據(jù)進(jìn)行說(shuō)明。如采用手工分配的方式，使得681名學(xué)生中414名同學(xué)分的了題目，滿意度為60.82%；如果采用最大匹配算法進(jìn)行分配，可以使分配數(shù)達(dá)到最大，有517名學(xué)生分得題目，滿意度上升為79.99%；最有用最有匹配算法進(jìn)行分配，使總體滿意度達(dá)到78.24%，533人。需要說(shuō)明的一點(diǎn)是，KM算法只是找到了整體最優(yōu)匹配而不是最大數(shù)匹配，如果整體最優(yōu)情況下匹配數(shù)和最大匹配數(shù)相差得太大的話，那么整體最優(yōu)方案顯得不太可取。所以，最好的情況就是同時(shí)考慮最優(yōu)匹配和最大匹配來(lái)同時(shí)控制兩者的大小。

4 結(jié)語(yǔ)

本系統(tǒng)實(shí)現(xiàn)了畢業(yè)論文選系統(tǒng)工作的各個(gè)管理功能，通過(guò)實(shí)現(xiàn)教師與學(xué)生的雙向選擇，使用KM算法，提高選題的質(zhì)量和效率，為學(xué)院充分利用網(wǎng)絡(luò)完成畢業(yè)論文選題工作提供了便利的平臺(tái)。

參考文獻(xiàn)：

[1]湯穎.畢業(yè)設(shè)計(jì)立項(xiàng)與選題管理及支持系統(tǒng)[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2006，29（5）.

篇（4）

中圖分類(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ù)主要有: 模式匹配、專家系統(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次或多次，則稱匹配成功，否則稱匹配失敗。

單模式匹配算法：在目標(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ǔ)上提出了一種快速模式匹配算法，稱為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ò)安全。

篇（5）

中圖分類(lèi)號(hào)：TP393.08

藏文網(wǎng)絡(luò)輿情是當(dāng)前必須關(guān)注的輿論涌現(xiàn)與信息傳播現(xiàn)象。近幾年藏文網(wǎng)絡(luò)輿情的數(shù)量呈現(xiàn)遞增的增長(zhǎng)趨勢(shì)，網(wǎng)絡(luò)信息的傳播途徑也呈現(xiàn)出多樣化和復(fù)雜化。由于藏文網(wǎng)絡(luò)的這些顯著的特點(diǎn)，藏文信息處理相對(duì)滯后于英文和中文等，短時(shí)間內(nèi)迅速的獲取大量信息則不容易。另，目前藏文網(wǎng)站大量的涌現(xiàn)，網(wǎng)頁(yè)數(shù)量巨大，處理起來(lái)速度相對(duì)慢，以往藏文網(wǎng)絡(luò)輿情頁(yè)面的統(tǒng)計(jì)都是基于手工統(tǒng)計(jì)實(shí)現(xiàn)的，效率低，很難對(duì)網(wǎng)絡(luò)輿情的變化做出快速響應(yīng)。模式匹配技術(shù)是內(nèi)容過(guò)濾的核心技術(shù)，是計(jì)算機(jī)信息技術(shù)領(lǐng)域研究的基礎(chǔ)問(wèn)題之一，研究敏感詞作為模式串的藏文模式匹配算法具有重要的研究意義。

BM算法是Boyer和Moore提出的一種字符串快速匹配算法。其基本思想是從右向左的把模式字符串同文本做比較。開(kāi)始時(shí)仍是P的最左邊與T的最左邊對(duì)齊，當(dāng)在某一趟比較中出現(xiàn)不匹配時(shí)，計(jì)算模式串右移的距離，把模式串向右移動(dòng)該距離，再進(jìn)行從右至左的匹配，同時(shí)應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來(lái)決定向右跳躍的距離。

1 BM算法在藏文中的改進(jìn)

藏文字符匹配中應(yīng)用BM算法時(shí)，必須結(jié)合藏文文字特征，對(duì)BM算法進(jìn)行改進(jìn)以符合藏文的特點(diǎn)，提高匹配效率。

1.1 藏文文字結(jié)構(gòu)及編碼特點(diǎn)

藏文是由多個(gè)基本字符通過(guò)縱向疊加組成的字符串，構(gòu)成一個(gè)完整藏文詞素的基本單位是由藏文中的“音節(jié)分割符tsheg bar”來(lái)確定。一個(gè)或多個(gè)音節(jié)構(gòu)成一個(gè)藏文詞。音節(jié)，則是由音節(jié)分割符（音節(jié)點(diǎn)）或者其他藏文標(biāo)點(diǎn)符號(hào)來(lái)劃分的。一個(gè)音節(jié)中基字符是不能被省略的，其余相關(guān)構(gòu)件都可以減少掉一個(gè)或幾個(gè)這樣仍然可以成一個(gè)音節(jié)（藏字）。七個(gè)構(gòu)件中輔音字母在各部位依據(jù)藏文語(yǔ)法要求都有一定限制并不是所有的輔音字母都能夠做前加字或者后加字等。

藏文在計(jì)算機(jī)中進(jìn)行編碼時(shí)一個(gè)音節(jié)需要用多個(gè)編碼來(lái)表示，長(zhǎng)度是不定的，這使得藏文在信息系統(tǒng)中的實(shí)現(xiàn)非常的麻煩。

（1）國(guó)內(nèi)的幾種藏文處理系統(tǒng)將藏文作為整字給予編碼。將藏文垂直組合的部分作為一個(gè)處理單元編碼（預(yù)先進(jìn)行垂直組合，稱為垂直預(yù)組合，垂直預(yù)組合后的字符稱為藏文字丁），比如北大方正的報(bào)刊排版系統(tǒng)、華光藏文排版和同元藏文處理系統(tǒng)、激光照排系統(tǒng)等，這幾個(gè)系統(tǒng)都有各自的編碼方案這類(lèi)編碼采用雙字節(jié)進(jìn)行編碼。這樣，具有完整構(gòu)件組合的藏字（即一個(gè)音節(jié)最多由4個(gè)字丁組成）。因此，國(guó)內(nèi)的這幾種編碼方式一個(gè)音節(jié)就最多有4個(gè)編碼。國(guó)家標(biāo)準(zhǔn)的擴(kuò)A和擴(kuò)B編碼方案采用的是也是整字編碼方案。

（2）國(guó)外的幾種藏文編碼方式也是采用整字編碼方案，但是將帶元音的字丁與元音分離后分別進(jìn)行了編碼。一個(gè)藏文音節(jié)最多就由5個(gè)字丁組成，即一個(gè)藏文音節(jié)由5個(gè)編碼組成。

（3）ISO/IEC 10646藏文基本集是國(guó)際標(biāo)準(zhǔn)的編碼方案，它完全將藏文視做拼音文字，字丁則是通過(guò)字母的動(dòng)態(tài)組合實(shí)現(xiàn)的。即將一個(gè)藏文音節(jié)拆分成不同構(gòu)件的獨(dú)立的部分，對(duì)每一個(gè)構(gòu)件都單獨(dú)進(jìn)行編碼。采用國(guó)際標(biāo)準(zhǔn)后一個(gè)藏文音節(jié)最多由7個(gè)編碼組成。基于不同編碼的方式使得一個(gè)音節(jié)的編碼個(gè)數(shù)不同，即使具有相同編碼個(gè)數(shù)的同一種編碼方案，由于編碼范圍不同編碼值也將不一致。1997年，我國(guó)的藏文基本字符集被收入了國(guó)際標(biāo)準(zhǔn)ISO/IEC 10646《信息技術(shù)通用多八位編碼字符集》。藏文編碼標(biāo)準(zhǔn)得到了統(tǒng)一。故本匹配算法以小字符集國(guó)際編碼標(biāo)準(zhǔn)（ISO/IEC 10646）編碼進(jìn)行討論。

依據(jù)藏文采用小字符集編碼中音節(jié)字的特點(diǎn)：

（1）具有完整構(gòu)件的音節(jié)具有7個(gè)編碼且每個(gè)編碼都是兩個(gè)字節(jié)，則對(duì)一個(gè)藏文音節(jié)字的表示則最多需要14個(gè)字節(jié)，最少也需要兩個(gè)字節(jié)。匹配過(guò)程中只有在一個(gè)音節(jié)的所有字節(jié)都相等的情況下，一個(gè)藏文音節(jié)才匹配成功。

（2）藏文音節(jié)與音節(jié)之間由音節(jié)點(diǎn)分割，在小字符集中該音節(jié)點(diǎn)為0X0F0B。

1.2 基于藏字特征改進(jìn)的BM算法

改進(jìn)后的BM模式匹配算法的具體思路：

（1）用模式串P的尾字符與文本串T進(jìn)行比較，結(jié)果失配，且文本串字符不為音節(jié)點(diǎn)，則模式串P右移到下一個(gè)出現(xiàn)的音節(jié)點(diǎn)處在新的位置繼續(xù)比較。

（2）用模式串P的尾字符與文本串T進(jìn)行比較，結(jié)果匹配，再把模式串第一個(gè)字符與文本串T比較，結(jié)果匹配。則將模式串與文本串T由右向左依次比較。當(dāng)所有字符都能匹配上時(shí)，則找到字符串返回查找結(jié)果并結(jié)束；如果模式串第一個(gè)字符與文本串T比較，結(jié)果不匹配，則：

求move（o）=First（OT）-First（OP），將模式串移動(dòng)move（o）個(gè)字符。

其中First（OT）：表示文本串T出現(xiàn)的第一個(gè)音節(jié)點(diǎn)；First（OP）：表示模式串P出現(xiàn)的第一個(gè)音節(jié)點(diǎn)。move（o）：距離差值；

（3）用模式串P的尾字符與文本串T進(jìn)行比較，結(jié)果匹配，再把模式串第一個(gè)字符與文本串T比較，結(jié)果匹配。則將模式串與文本串T由右向左依次比較。如果在模式串P的某一字符x失配，則轉(zhuǎn)4；

（4）如果失配的字符x在模式P中沒(méi)有出現(xiàn)，則：

求：First（x）：從x起始的字符到第一個(gè)出現(xiàn)的音節(jié)點(diǎn)的距離。那么從字符x開(kāi)始的m（模式串的長(zhǎng)度）+First（x）個(gè)文本顯然不可能與P匹配成功，直接全部跳過(guò)該區(qū)域即可，則模式串移位m+First（x）個(gè)位置；

（5）如果失配的字符x在模式P中出現(xiàn)，則：以該字符進(jìn)行對(duì)齊。設(shè)move（x）為P右移的距離，m為模式串P的長(zhǎng)度，max（x）為字符x在P中最右位置。作模式串移位：[m-max（x）]+First（x）。

通過(guò)上對(duì)面算法的分析，我們可以看出，改進(jìn)后的BM算法可以減少比較的次數(shù)，提高匹配的速度。

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

越來(lái)越多的藏文出版作品在以數(shù)字化方式存儲(chǔ)，網(wǎng)絡(luò)上的藏文資料也日益增多，改進(jìn)針對(duì)西文以及中文的搜索算法，尋找適合藏文文字特點(diǎn)的字符查找算法是值得研究的。改進(jìn)的BM模式匹配算法就是利用藏文字符構(gòu)字特征以及編碼特點(diǎn)，改變了BM算法的比對(duì)方式，從而提高匹配的效率。

參考文獻(xiàn)：

[1]江濤，于洪志.基于藏文文本的網(wǎng)絡(luò)輿情監(jiān)控系統(tǒng)研究[A].全國(guó)計(jì)算機(jī)安全學(xué)術(shù)交流會(huì)論文集[C]，2006.

[2]閔聯(lián)營(yíng)，趙婷婷.BM算法的研究與改進(jìn)[J].武漢理工大學(xué)學(xué)報(bào)，2006（03）：528-530.

[3]殷麗華，張冬艷，方濱興.面向入侵檢測(cè)的單模式匹配算法性能分析[J].計(jì)算機(jī)工程與應(yīng)用，2004（24）：46-47.

[4]扎西加，珠杰.面向信息處理的藏文分詞規(guī)范研究[J].中文信息學(xué)報(bào)，2009（04）：113-117.

[5]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1999.

篇（6）

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)25-6122-02

Research of the Text Subjective Question's Auto Remarking Algorithm Based on Word Segmentation Algorithm &VSM

LI Xue-jun

(Southwest University of Science and Technology, Mianyang 621010, China)

Abstract: The paper makes use of the studied results(such as Vector Space Model (VSM), Word Segmentation algorithm and so on) of the native language understanding, and applys them in processing the text subjective question's answer (including the standard answer and the student's answer), and then it used the text_charactered vector matching algorithm to auto remark those student's examining paper by the computer system. According to the experiment, the algorithm has accuracy of remarking and some valuable domains of application.

Key words: Auto-remarking; Word Segmentation algorithm; Vector Space Model (VSM); Text character matched

隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)技術(shù)迅猛發(fā)展，傳統(tǒng)教育模式發(fā)生了變化，越來(lái)越多的課程提出了在線考試的需求。計(jì)算機(jī)可以很好地完成客觀題（如選擇題、判斷題）的判分工作，其判分策略、關(guān)鍵技術(shù)及其應(yīng)用實(shí)例詳見(jiàn)文獻(xiàn)[1]至文獻(xiàn)[3]。亦即把考生作答的結(jié)果和題目標(biāo)準(zhǔn)答案進(jìn)行精確匹配從而得到考生的得分。文獻(xiàn)[4]提出了一種近似串匹配算法來(lái)對(duì)文本錄入題的自動(dòng)評(píng)分算法，其本質(zhì)還是進(jìn)行文本的比較，與客觀題的判分原理基本是相同的。

計(jì)算機(jī)自動(dòng)評(píng)分是指利用計(jì)算機(jī)程序來(lái)模擬人工評(píng)分的標(biāo)準(zhǔn)和內(nèi)部過(guò)程。對(duì)客觀題的評(píng)分是通過(guò)把試題的標(biāo)準(zhǔn)答案與考生的答案做一個(gè)精確比較，并據(jù)此作為是否給學(xué)生相應(yīng)的題目分值；對(duì)于主觀題，目前一般是讓考生把其作答的結(jié)果形成一個(gè)文件（答案文件），再通過(guò)網(wǎng)絡(luò)把考生的答案文件上傳到考試服務(wù)器中的專用目錄中，科任教師在考試結(jié)束后對(duì)考生的答案文件進(jìn)行人工評(píng)判來(lái)進(jìn)行給分；最后把考生客觀題的計(jì)算機(jī)自動(dòng)評(píng)分結(jié)果和主觀題的人工評(píng)分結(jié)果累加起來(lái)作為考生的最終成績(jī)。對(duì)于客觀題可以完全不要人工干預(yù)，而主觀題就必須在人工干預(yù)下才能完成。

因此本文就此提出將人工智能的自然語(yǔ)言理解技術(shù)（主要是分詞算法）、文本的空間向量模型表示和知識(shí)的框架表示內(nèi)容應(yīng)用到網(wǎng)絡(luò)考試系統(tǒng)中的主觀題的自動(dòng)評(píng)分過(guò)程中。

1 文本主觀題自動(dòng)評(píng)分原理

對(duì)于在線考試系統(tǒng)來(lái)說(shuō)，其自動(dòng)評(píng)分是在特定范圍內(nèi)的，不需要讓其理解所有的自然語(yǔ)言，只需要理解標(biāo)準(zhǔn)答案即可。因此，應(yīng)該使用某種算法使標(biāo)準(zhǔn)答案轉(zhuǎn)化成機(jī)器能夠理解的形式，將考生答案也按照一定的規(guī)則轉(zhuǎn)化成計(jì)算機(jī)可以理解的形式，然后再將其和標(biāo)準(zhǔn)答案進(jìn)行匹配并評(píng)分。其關(guān)鍵是如何將評(píng)分規(guī)則轉(zhuǎn)化為可以被機(jī)器理解的知識(shí)庫(kù)。主觀題的自動(dòng)評(píng)分原理如圖1所示。

2 自動(dòng)分詞算法簡(jiǎn)介

2.1 最大匹配分詞算法

匹配分詞法是按照一定的策略將待切分的漢字串與一個(gè)“充分大的”機(jī)器詞典（如金山詞霸等）中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串，則匹配成功（識(shí)別出一個(gè)詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配。按照不同長(zhǎng)度優(yōu)先匹配的情況，可以分為最大（最長(zhǎng)）匹配和最?。ㄗ疃蹋┢ヅ?。最大匹配分詞法即先確定一個(gè)最大的詞的長(zhǎng)度，然后從左（正向）或從右（逆向）取該長(zhǎng)度的詞串，將詞串與詞典中的詞條匹配，如果沒(méi)有該詞則去掉一個(gè)字符繼續(xù)匹配，以此類(lèi)推，直到達(dá)到匹配或剩下一個(gè)單字為止。

2.2 最大概率分詞算法

最大概率分詞算法的基本思想是：假設(shè)一個(gè)待切分的漢字串可能包含多種分詞結(jié)果，將其中概率最大的那個(gè)作為該字串的分詞結(jié)果。例如，有一個(gè)句子S＝“有意見(jiàn)分歧”，第一種分詞路徑W1＝“有/意見(jiàn)/分歧/”，第二種分詞路徑W2＝“有意/見(jiàn)/分歧/”，如圖2所示。到底應(yīng)該選擇哪一種為最后的分詞結(jié)果呢？

根據(jù)概率分詞算法的基本思想，需要計(jì)算每一種方法出現(xiàn)的選取概率的作為最后結(jié)果，即計(jì)算Max(P(W1|S), P(W2|S))。概率計(jì)算方法如圖3所示。

每一個(gè)詞匯出現(xiàn)的概率P(wi) 可以在帶詞頻的詞典中查出。通過(guò)查詞典可以得到每個(gè)詞的概率為：P(有)=0.0180，P(有意)=0.0005，P(意見(jiàn))=,0.0010，P(見(jiàn)) =0.0002，P(分歧)=0.0001。

對(duì)于第一種分詞方法：P(w1) = P(有) * P(意見(jiàn)) * P(分歧) = 1.8×10-9；

對(duì)于第二種分詞方法：P(w2) = P(有意) * P(見(jiàn)) * P(分歧) = 1×10-11；

由上所示，P(w1) > P(w2)，所以取第一種方法作為分詞結(jié)果。

3 文本矢量特征匹配算法

主觀試題的答案以文本方式存儲(chǔ)，經(jīng)過(guò)分詞后的文本如何表示才能更加容易地被計(jì)算機(jī)處理關(guān)系到文本處理的準(zhǔn)確性，因此文本表示方法是自動(dòng)評(píng)分算法的一個(gè)關(guān)鍵問(wèn)題。近年來(lái)，在Web文本信息特征獲取算法的研究中，矢量空間模型(Vector Space Model，VSM )[5-6]是應(yīng)用較多且效果較好的方法之一，本算法借鑒了該模型的思想。在矢量空間模型中，文本被看作由一組正交詞條所生成的矢量空間。根據(jù)這個(gè)思想，同時(shí)考慮到考試評(píng)分中經(jīng)常將試題答案分為幾個(gè)要點(diǎn)，因此提出主觀題成績(jī)?cè)u(píng)判模型為：

首先，答案文本是由一些要點(diǎn)組成，如果把答案文本（Answer text 用A來(lái)表示）看成一個(gè)由n個(gè)要點(diǎn)（Pi）組成的集合，則可以這樣表示答案：A={P1,P2,…,Pi,…,Pn}；設(shè)每個(gè)要點(diǎn)Pi的分值為Mi，則該答案的總分M為：；按照VSM思想，將標(biāo)準(zhǔn)答案每一個(gè)要點(diǎn)Pi被看成是由Ki個(gè)特征詞（wj）組成的向量P：；設(shè)每個(gè)特征詞的權(quán)重是wj（由經(jīng)驗(yàn)豐富的任課教師人工設(shè)置），則其歸一化權(quán)重為：；設(shè)考生答案的每一個(gè)要點(diǎn)Pi'也被看成是由Ki'個(gè)特征詞（wj'）組成的向量P'：；通過(guò)計(jì)算考生答案和標(biāo)準(zhǔn)答案的向量間的距離并據(jù)此計(jì)算考生可得到到該要點(diǎn)的分值，即：(如果向量間的距離為0，則說(shuō)明考生答案和標(biāo)準(zhǔn)答案完全匹配，考生可以拿到該要點(diǎn)的所有分值)；考生所得總分M'為：。

4 算法測(cè)試及結(jié)論

本論文采用oracle作為后臺(tái)數(shù)據(jù)庫(kù)管理系統(tǒng)（因?yàn)橄到y(tǒng)所用的詞典數(shù)據(jù)庫(kù)都比較大），基于B/S模式設(shè)計(jì)了基于文本的主觀題自動(dòng)評(píng)分測(cè)試軟件。通過(guò)對(duì)不同名詞解釋題目（答案長(zhǎng)度及復(fù)雜度不同）的評(píng)測(cè)，再將本算法評(píng)得的分?jǐn)?shù)與人工評(píng)分相比，分?jǐn)?shù)的容差在（－0.5～＋0.5），可以測(cè)得其評(píng)分的準(zhǔn)確度在86.93％。通過(guò)實(shí)際的數(shù)據(jù)測(cè)試可以看出，答案越復(fù)雜，要點(diǎn)越多，評(píng)分的準(zhǔn)確性越差；相反，要點(diǎn)越少，答案越簡(jiǎn)單，評(píng)分的準(zhǔn)確性越好。而且人工設(shè)置關(guān)鍵詞和權(quán)重也有利有弊，人工設(shè)置固然增強(qiáng)了系統(tǒng)的準(zhǔn)確程度，但是其前提是設(shè)置人必須是有經(jīng)驗(yàn)的老師，如果是沒(méi)有經(jīng)驗(yàn)的老師設(shè)置，則給算法增加了人為的誤差。該算法具有一定的實(shí)用性，但還有待進(jìn)一步的完善。

參考文獻(xiàn)：

[1] 華蕊. 自動(dòng)組卷及評(píng)分系統(tǒng)的設(shè)計(jì)[J]. 中國(guó)電化教育.2002,(2):84-85.

[2] 朱映輝, 江玉珍.計(jì)算機(jī)自動(dòng)評(píng)卷策略分析與研究[J]. 電腦知識(shí)與技術(shù),2005,(35):30-32.

[3] 李丁. 計(jì)算機(jī)考試系統(tǒng)中自動(dòng)評(píng)分策略的研究與實(shí)現(xiàn)[J]. 廣東廣播電視大學(xué)學(xué)報(bào),2002,11(4):30-32.

篇（7）

中圖分類(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ù)稱之為數(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)方法,也稱為迭代最近點(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ò)充。基于ICP算法點(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)樗捎玫氖侨炙阉?。為適應(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.

篇（8）

中圖分類(lèi)號(hào)：TP399 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)23-5698-03

NCC Algorithm Optimization Based on the Wavelet Multi Scale

FU Yan-li

(Shandong SHENG DA Construction Group Limited Company, Jining 272000, China)

Abstract: Algorithms based on pixel gray value are already very common in mage template matching problem, which normalized cross correlation algorithm (Normalized CROSS Correlation. NCC) is one of the classic algorithm based on gray matching, and is widely applied, but the algorithm also has the disadvantages of high time complexity. Multi scale theory and the multiple resolution image are representation and analysis of relevant, i.e. a digital image can be expressed as a multiple resolution sub-images collection. Its characteristic cannot be found in a resolution while in the characteristics of another resolution is easy to find, the wavelet multi-scale analysis is an important tool, known as mathematical microscope, can be used to construct different adaptive filter with improved filter convergence, which is also one of the advantages of wavelet transform. Image after wavelet decomposition, in the lowest layer of the low frequency sub image resolution, retaining only the most information of image, that is after wavelet transform of image of a feature. Based on the wavelet multi scale NCC algorithm not only optimize the algorithm itself at the same time optimization based on gray matching search path, so that guarantee the NCC algorithm accuracy, and reduce the matching time, and also the simulation experiments show that this algorithm is effective.

Key words: image matching; normalized cross algorithm; wavelet transform; multi-scale; tower structure

圖像匹配是對(duì)兩幅圖像找其對(duì)應(yīng)的映射關(guān)系或根據(jù)已知模式到另一副圖中尋找相應(yīng)的模式。圖像匹配是一種極其重要的圖像處理和分析技術(shù)，無(wú)論在圖像理解還是在視覺(jué)計(jì)算中都具有重要作用和地位，其成功應(yīng)用到航空航天、地球物理信息、海洋船載導(dǎo)航和地理特征探測(cè)、工業(yè)生產(chǎn)、醫(yī)療衛(wèi)生等，因此圖像匹配技術(shù)越來(lái)越受到人們的重視和青睞。

圖像匹配的實(shí)用的技術(shù)方法一般分為兩大類(lèi)，即基于灰度匹配和基于特征匹配?；诨叶绕ヅ涫前汛ヅ鋱D像中的某一像素點(diǎn)的灰度鄰域作為匹配模板或者稱為子窗口，在參考圖中搜索具有相同或者相似灰度值分布的對(duì)應(yīng)的鄰域，從而實(shí)現(xiàn)兩副圖的匹配?；谔卣鞯膱D像匹配不是利用圖像中的像素值進(jìn)行匹配，而是通過(guò)灰度導(dǎo)出符號(hào)特征（如：拐點(diǎn)、角點(diǎn)、邊緣線段、圖像輪廓）實(shí)現(xiàn)圖像的匹配。前者作為一種基本的匹配方法之一，在很多地方得到了充分的應(yīng)用，可以充分利用圖像的所有信息、尤其適合在圖像僅有平移和模板圖像中非零項(xiàng)比較少的情況下，便于匹配的實(shí)現(xiàn)。但是弱點(diǎn)也是很明顯的，即對(duì)圖像的幾何變形、光照強(qiáng)度、對(duì)比度都很敏感，并且計(jì)算量大，不適合實(shí)時(shí)匹配。后者利用從圖像得到的符合特征作為匹配的基元，有效的克服了前者的弱點(diǎn)，但是特征匹配過(guò)于依賴圖像的特征點(diǎn)，并且特征點(diǎn)的提取涉及到幾何和圖形形態(tài)學(xué)的計(jì)算，沒(méi)有統(tǒng)一的模型可以利用，需要對(duì)不同圖像選擇不同的自適應(yīng)特征，需要額外的特征提取的計(jì)算，往往計(jì)算也比較復(fù)雜。

1 歸一化交叉相關(guān)算法

歸一化交叉相關(guān)算法[1] (Normalized Cross Correlation．簡(jiǎn)稱NCC)定義如下：

假設(shè)模板圖像w(s,t)的尺寸為m×n，其中m,n往往取奇數(shù)，參考圖像f(x,y)是一個(gè)大小為M×N，（1≤m≤M, 1≤n≤N），則：

（1）

其中a=(m-1)/2,b=(n-1)/2

由于表示模板的能量所以是一個(gè)常量，，當(dāng)模板移動(dòng)距離比較小時(shí)，也近似一個(gè)常量，所以為使D(x,y)最小則需要達(dá)到最大值，由于對(duì)w(s,t)和f(x,y)的副值的變化比較敏感，所以定義歸一化互相關(guān)函數(shù)為：

（2）

其中a=(m-1)/2,b=(n-1)/2

為了進(jìn)一步克服噪聲的影響和理想狀態(tài)匹配時(shí)C(s,t)相同值太多，還進(jìn)一步簡(jiǎn)化（2）式即：

（3）

其中a=(m-1)/2,b=(n-1)/2，Ef,Ew分別為f(x,y)和w(s,t)的期望。

當(dāng)C(s,t)達(dá)到最大值時(shí)，兩圖匹配成功。

通過(guò)對(duì)NCC算法的理論分析，不難發(fā)現(xiàn)：為了讓算法達(dá)到理想狀態(tài)進(jìn)行圖像匹配，犧牲時(shí)間，換取了理想的匹配。通過(guò)對(duì)公式（1）（2）（3）分析，可以看出公式越來(lái)越復(fù)雜，計(jì)算量越來(lái)越大，匹配的時(shí)間越來(lái)越多，由于小波變換可以作為一個(gè)平滑過(guò)濾器來(lái)使用，所以小波變換可以消除圖像的幅值和圖像的噪音，因此選擇了NCC算法的中的公式（1），這樣就可以節(jié)省大量的計(jì)算時(shí)間，提高匹配的速度。

2 小波變換的多尺度分析

小波在1987年首次作為分析工具首次出現(xiàn)，小波是多尺度分析的重要工具，被譽(yù)為數(shù)學(xué)上的顯微鏡[3]，因?yàn)樾〔ㄗ儞Q具有時(shí)間-頻率局部化的特點(diǎn)，即在小波變換中，時(shí)間窗函數(shù)的寬度與頻域函數(shù)窗口的函數(shù)的都是一個(gè)常數(shù)，根據(jù)測(cè)不準(zhǔn)原理，他們的乘積也是一個(gè)常數(shù)。在對(duì)低頻分析是可以加寬時(shí)間窗，減少頻率窗；而對(duì)于高頻分析是，可以增高頻率窗，減少時(shí)間窗，這種特性被稱為“自適應(yīng)窗口特性”所以小波的這種特性是小波變換能提高為多尺度分析的基礎(chǔ)，可以用來(lái)構(gòu)建不同的自適應(yīng)濾波器以改進(jìn)濾波器的收斂性。

小波多尺度分析的表示：以多分辨率來(lái)解釋圖像的一種有效并且容易理解的結(jié)構(gòu)就是圖像金字塔如圖1。一副圖像金字塔是一系列以金字塔形式排列的分辨率逐層降低的圖像集合。0層是N×N的圖像，對(duì)0層的圖像進(jìn)行小波亞抽樣，可以達(dá)到一個(gè)原圖四分之一的較粗略的縮略圖。這個(gè)過(guò)程是可以重復(fù)進(jìn)行直到N層，這時(shí)圖像是1×1的圖像。這時(shí)圖像的分辨率也從0層最高到N層逐次下降，是原來(lái)圖像的四分之一。這樣一個(gè)圖像的金字塔結(jié)構(gòu)共（logN 2+1）層，或者有這么多不同的圖像組成，并且圖像所用的容量只是原來(lái)的圖像的4/3N2。

多尺度小波的特點(diǎn)[3]：1）多尺度小波具有窗口自適應(yīng)的特性，即可以使圖像的小波分析聚集到間斷點(diǎn)、奇異點(diǎn)和邊緣，體現(xiàn)了局部特點(diǎn)；同時(shí)也可以獲得全局的視點(diǎn)。這個(gè)特性是小波變換獨(dú)有的，對(duì)非穩(wěn)定性和快速變換的信號(hào)的分析特別有用的。2）小波變換相當(dāng)于一組多分辨率的帶通濾波器。利用這個(gè)特性，可以將圖像的信號(hào)分解為如圖1所示的頻率子帶上，在每個(gè)子帶可以用小波變換進(jìn)行處理。3）多尺度小波分解圖像的所有子圖的和等于原圖像的大小，即不增加存儲(chǔ)空間。4）分解后的圖像，沒(méi)有信號(hào)損失，保證圖像的完整性，便于對(duì)低頻和高頻的處理和上層對(duì)下層的實(shí)時(shí)重建。

3 基于小波多尺度的匹配算法

多尺度小波匹配主要利用了小波多尺度的特性對(duì)待配圖和參考圖進(jìn)行金字塔式分解，結(jié)構(gòu)如圖1，匹配基本流程如圖2所示，具體步驟如下：

1）首選判斷待配圖和參考圖的大小，一般待配圖比參考圖像小多，這時(shí)就是在參考圖中尋找待配圖的位置；反之就是在待配圖中搜索作為目標(biāo)的參考圖的過(guò)程。兩者原理是一樣的，所以匹配算法是基于前者論述和測(cè)試的。

2）判斷待配圖和參考圖的灰度光照強(qiáng)度、對(duì)比度、物體在拍攝時(shí)的遮擋情況以及空間幾何等，這些都會(huì)對(duì)基于灰度匹配造成錯(cuò)誤的匹配，進(jìn)行圖像匹配前的預(yù)處理。

3）以上兩步看作圖像預(yù)處理的過(guò)程。接下來(lái)選擇小波，這步非常重要，本課題選擇了Daubechies（db4）小波，因?yàn)榇诵〔ㄔ谶\(yùn)動(dòng)估計(jì)中應(yīng)用非常廣泛，可以很好的保留低頻中圖像的絕大部分信息，去掉高頻信號(hào)中的噪聲，是一個(gè)行之有效的小波。然后利用小波的多尺度特性將待配圖和參考圖像分解為N層，結(jié)構(gòu)如圖1，待配圖和參考圖未分解的圖像為0層（有些文獻(xiàn)是將原圖定義1層），從低到上，分解的最大層為N層（或者分解的最大尺度為N層），在MATLAB中實(shí)現(xiàn)小波變換的最大層的函數(shù)是wmaxlev()。但是為了保證低頻的中含有未解圖的絕大部分信息，尤其是灰度變化比較劇烈的區(qū)域，一般分解的層次為：一維分解的分解尺度N不超過(guò)5；二維的分解尺度N不超過(guò)3。第N層圖像的尺寸和大小都是原圖來(lái)1/(N+1)2。

4）通過(guò)前三步，待配圖和參考圖的原圖被分為N層不同頻率子圖的集合，現(xiàn)在可以在分辨率最低的N層進(jìn)行待配圖的子圖與參考圖的子圖進(jìn)行匹配。采用了經(jīng)典灰度相似度量算法：歸一化交叉相關(guān)算法NCC進(jìn)行對(duì)待配圖和參考圖進(jìn)行匹配。整個(gè)匹配過(guò)程就是將N層的待配圖看作模板，匹配的實(shí)現(xiàn)基本過(guò)程：1）在第N層利用歸一化交叉相關(guān)算法NCC進(jìn)行匹配，即求出（1）式的最大值；找出對(duì)應(yīng)匹配區(qū)域；2）在N-1層按照N層的算法，再在對(duì)應(yīng)匹配區(qū)域進(jìn)行NCC匹配；3）重復(fù)第5步直到0層；4）輸出匹配結(jié)果。

4 仿真實(shí)驗(yàn)

本算法使用Matlab2007b進(jìn)行了大量的仿真實(shí)驗(yàn)，圖3是選擇了最著名lena圖進(jìn)行算法的仿真說(shuō)明。

結(jié)果分析：

1）為了與其他文獻(xiàn)在匹配速度和精確度的可比性，選擇了其中的一組著名圖像：lena圖，如圖3和圖4中的A圖所示。進(jìn)行尺度為2的小波分解，兩幅圖像中的尺度為2的低頻子圖，基本上無(wú)法辨認(rèn)，即所需要的信息基本上都被過(guò)濾，所以在第2層匹配是無(wú)法匹配的，根據(jù)第4節(jié)的匹配步驟，只能在第1層子圖匹配，匹配實(shí)驗(yàn)的結(jié)果證明是可行的。

2）將這幅lena的待配圖和參考圖如表1所示的各種算法進(jìn)行匹配。通過(guò)表1可以看出，此算法是可行的。

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

論文的創(chuàng)新是首選剖析了NCC算法，選擇了算法的中間過(guò)渡式作為本算法的一部分，好處是減少圖像匹配的計(jì)算量，同時(shí)也保證了匹配的精確度；采用了小波變換的多尺度特性，優(yōu)化了匹配的搜索策略，提高了匹配的精確度和匹配的時(shí)間，所以結(jié)合兩者的特點(diǎn)可以很好的完成某些領(lǐng)域中圖像的實(shí)時(shí)匹配。

參考文獻(xiàn)：

[1] Gongzalez R C,Woods R E.Digital Image Processing[M].2nd Edition (DIP/2e).北京:電子工業(yè)出版社,2005.

[2] 李強(qiáng),張鈸.一種基于圖像灰度的快速匹配算法[J].軟件學(xué)報(bào),2006,17(2):216-222.

[3] Luigi Di Stefan.Stefano Mattoccia Fast template matching using bounded panial correlation[J].Machine Vision and Applications,2003(13):213-221.

[4] Bamea D I,Silverman H F.A class of algorithms for fast digital image registration[J].IEEE Trans on Computers,1972,C-21:179-186.

[5] 鄭運(yùn)平,陳傳波.一種新的灰度圖像表示算法研究[J].計(jì)算機(jī)學(xué)報(bào),2010,33(12):2398-2406.

[6] 李健,梁琨.基于小波多分辨率分析的快速圖像匹配[J].陜西科技大學(xué)學(xué)報(bào),2006,24(6):81-84.

[7] 劉瑩.基于灰度相關(guān)的圖像匹配算法的改進(jìn)[J].應(yīng)用光學(xué),2007,28(5):537-540.

[8] 杜杰.兩種基于灰度的快速圖像匹配算法[D].大連:大連海事大學(xué),2007.

[9] 范俐捷,王巖飛.一種新的基于灰度的圖像匹配方法[J].微計(jì)算機(jī)信息,2007,23(30):296-297.

篇（9）

1 最小二乘法影像匹配的基礎(chǔ)理論與算法

影像匹配實(shí)際上就是兩幅（或者多幅）影像之間識(shí)別同名點(diǎn)，它是計(jì)算機(jī)視覺(jué)及數(shù)字?jǐn)z影測(cè)量的核心問(wèn)題。我們知道要匹配的點(diǎn)的同名像點(diǎn)肯定在其同名核線上。在進(jìn)行最小二乘影像匹配之前，需要先進(jìn)行粗匹配。然后在粗匹配的基礎(chǔ)上用最小二乘法進(jìn)行精匹配。我們這次討論的是利用一維搜索的方法來(lái)進(jìn)行粗匹配。這就是利用同名核線來(lái)進(jìn)行同名像點(diǎn)的粗匹配。這相對(duì)于二維匹配來(lái)說(shuō)速度更快。

1.1基于數(shù)字影像幾何糾正法提取核線，利用共面條件來(lái)確定同名核線

我們知道，核線在航空攝影測(cè)量上是相互不平行的，它們相交于一點(diǎn)---核點(diǎn)。但是如果將影像上的核線投影（或者稱為糾正）到一對(duì)“相對(duì)水平”-------平行于攝影基線的影像對(duì)上后，則核線相互平行。正是由于“水平”的像片具有這么一特性，我們就有可能在“水平”像片上建立規(guī)則的格網(wǎng)，它的行就是核線，核線上像元素（坐標(biāo)為xt、yt）的灰度可由它對(duì)應(yīng)的實(shí)際像片的像元素的坐標(biāo)為x，y的灰度求的 ，即g（xt，yt）=g（x，y）。

根據(jù)前邊的共線方程，同一攝站點(diǎn)攝取的水平像片與傾斜像片，其水平和傾斜像片的坐標(biāo)之間的關(guān)系為：

(1-1-1)

(1-1-2)

上邊的式子中a1,a2…,c3為左片的九個(gè)方向余弦，是該像片的外方位角素的函數(shù)，f為像片主距。顯然在水平像片上，當(dāng)yt為常數(shù)的時(shí)候，則為核線,將yt=c代入（1-1-1）和（1-1-2）式經(jīng)整理，得：

（1-1-3）

其中：

e3=d3

若在“水平”像片上以等間隔獲取一系列xt值 ，(k+1)*,(k+2)*…,可以得到一系列的像片坐標(biāo)（x1，y1），（x2，y2），（x3，y3），…，這些點(diǎn)就位于傾斜像片p的核線上。

同樣以yt=c 代入右邊的共線方程：

(1-1-4)

(1-1-5)

其中， ， ，… 右方像片的對(duì)于單獨(dú)像對(duì)像空間輔助坐標(biāo)的角方位元素的函數(shù)，由此可得右片上的同名核線。

1.2核線的重排列（重新采樣）

已知原始的影像的灰度序列，為求待定的平行于基線的“水平”影像。這就需要進(jìn)行核線的灰度重采樣。按照式（1-1-1）和（1-1-2）將“水平”像片上的坐標(biāo)u，v反算到原始影像上的x，y。但是由于所求得的像點(diǎn)不一定恰好都落在原始影像采樣的像元中心，這就必須進(jìn)行灰度的內(nèi)插-----重采樣。通常所用到的是雙線形插值法，取臨近的四個(gè)像元點(diǎn)的灰度的數(shù)值進(jìn)行待求點(diǎn)的灰度的計(jì)算。

圖1-2-1雙線形重采樣

本公式中y1代P點(diǎn)到g1，g4連線的距離，x1代表P點(diǎn)到g3,g2連線的距離的大小

1.3數(shù)字影像匹配的基本算法

本論文講述的相關(guān)系數(shù)法主要是對(duì)于一維影像相關(guān)的。

如圖1-3-1所示是一維影像相關(guān)的目標(biāo)區(qū)和搜索區(qū)（這里取m=n）。設(shè)g代表目標(biāo)區(qū)內(nèi)的點(diǎn)組的灰度值，g’代表搜索區(qū)內(nèi)相應(yīng)點(diǎn)組的灰度值，則每個(gè)點(diǎn)組共取得了n個(gè)點(diǎn)的灰度值的均值為

圖1-3-1一維相關(guān)目標(biāo)和搜索區(qū)域

，（i=0，1，2…n） （1-3-1）

兩個(gè)點(diǎn)組的方差 ， 分別為：

， （1-3-2）

兩個(gè)點(diǎn)組的協(xié)方差 為：

（1-3-3）

則兩個(gè)點(diǎn)組的相關(guān)系數(shù) 為：

（0,1,… -n） （1-3-4）

在搜索區(qū)內(nèi)沿核線尋找同名像點(diǎn)，每次移動(dòng)一個(gè)像素，按照（1-3-4）來(lái)依次相關(guān)系數(shù) ，取其中的最大的數(shù)值，其對(duì)應(yīng)的相關(guān)窗口的中心像素就被認(rèn)為是目標(biāo)點(diǎn)的同名像點(diǎn)。

1.4用相關(guān)系數(shù)的拋物線擬合來(lái)提高相關(guān)精度

為了把同名點(diǎn)求的更為準(zhǔn)確一些，可以把相關(guān)系數(shù)的最大點(diǎn)i點(diǎn)左右若干點(diǎn)（一般取左右個(gè)兩個(gè)點(diǎn)）聯(lián)系起來(lái)，從而將其函數(shù)的最大值k處的作為尋求的同名點(diǎn)的位置，結(jié)果會(huì)更好一些。

圖1-4-1拋物線擬合

如圖1-4-1所示設(shè)有相鄰像元素系處的5個(gè)相關(guān)系數(shù)，用一個(gè)二次拋物線方程式來(lái)擬合，取用的拋物線方程，代表相應(yīng)S位置處灰度的數(shù)值。

（1-4-1）

式中的參數(shù)A，B，C用間接平差方法求的。此時(shí)拋物線頂點(diǎn)k處的位置為：

（1-4-2）

由相關(guān)系數(shù)拋物線擬合可以使相關(guān)精度提高到0.15-0.2個(gè)子像素（當(dāng)信噪比較高的時(shí)候），但是相關(guān)精度和信噪比近似成反比例關(guān)系。當(dāng)信噪比比較小的時(shí)候，采用相關(guān)系數(shù)拋物線擬合也不能提高相關(guān)精度。

2僅考慮相對(duì)位移的一維最小二乘影像匹配

2.1一維最小二乘影像匹配原理

在本次僅僅考慮相對(duì)位移的一維最小二乘影像相關(guān)。在一維影像相關(guān)中是在傾斜影像相對(duì)應(yīng)的水平影像坐標(biāo)系中沿x軸方向?qū)で笸c(diǎn)，若在最小二乘算法中把搜索區(qū)像點(diǎn)移動(dòng)的位移量作為一個(gè)幾何參數(shù)引入，就可以直接解算像點(diǎn)的位移。

設(shè)有兩個(gè)一維灰度函數(shù) ， ，除了隨機(jī)噪聲 ， 外， 相對(duì)于 存在位移量 。如圖4-3-1所示，則

（2-1-1）

則（2-1-2）

圖 2-1-1 僅考慮相對(duì)位移的一維最小二乘影像相關(guān)

為了解求相對(duì)位移量，需要對(duì)（2-1-2）式子進(jìn)行線性化：

（2-1-3）

對(duì)離散的數(shù)字影像，灰度函數(shù)的導(dǎo)數(shù) 可以由差分 代替，即

（2-1-4）

其中 采樣間隔。令 ，則誤差方程式可以寫(xiě)為；

（2-1-5）

為了解求 ，取一個(gè)窗口，對(duì)窗口內(nèi)的每個(gè)像元素都可以列出一個(gè)誤差方程式，按照的原則，則可以求得影像的相對(duì)位移的量 ：

（2-1-6）

因?yàn)榻馑愣际蔷€性化的結(jié)果得到的，因此，解算需要迭代進(jìn)行。解得 后，對(duì) 進(jìn)行重新采樣，各迭代計(jì)算時(shí)，系數(shù) 以及常數(shù)項(xiàng) 均采用重新采樣后的灰度值進(jìn)行計(jì)算。

2.2計(jì)算最佳的匹配點(diǎn)位

我們知道，影像匹配的目的是為了尋求獲得同名點(diǎn)。通常以待定的目標(biāo)點(diǎn)建立一個(gè)目標(biāo)窗口，窗口的中心點(diǎn)就是目標(biāo)點(diǎn)。但是，在高精度影像相關(guān)中，必須考慮目標(biāo)窗口的中心點(diǎn)是否是最佳的匹配點(diǎn)。根據(jù)最小二乘法影像匹配的精度理論可以知道：影像匹配中的精度取決于影像灰度的梯度 ， 。因此，可以用梯度的平方為權(quán)，在左方影像窗口中內(nèi)對(duì)坐標(biāo)做加權(quán)平均：

（2-2-1）

以它作為目標(biāo)點(diǎn)坐標(biāo)，它的同名點(diǎn)坐標(biāo)可以由最小二乘法影像匹配所求得的幾何變換參數(shù)求得；

（2-2-2）

隨著以最小二乘法為基礎(chǔ)的高精度數(shù)字影像匹配算法的發(fā)展，為了近一步提高起可靠性與精度，攝影測(cè)量工作者進(jìn)而有提出了各種帶有約束條件的最小二乘影像匹配的算法。例如，附帶有共線條件的最小二乘相關(guān)以及與VLL法相結(jié)合的最小二乘影像匹配方法都得到了廣泛的應(yīng)用和研究。

3 最小二乘影像匹配的精度分析

篇（10）

引言

在計(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.