緒論：寫作既是個人情感的抒發，也是對學術真理的探索，歡迎閱讀由發表云整理的11篇匹配算法論文范文，希望它們能為您的寫作提供參考和啟發。

篇（1）

 

Rete算法是一個快速的模式匹配算法，它通過形成一個Rete網絡進行模式匹配，利用基于規則的系統的兩個特征，即時間冗余性（Temporalredundancy）和結構相似性（structural similarity），提高系統模式匹配效率。

一、模式匹配的基本概念

1、可滿足規則：一個規則稱為可滿足的，若規則的每一模式均能在當前工作存儲器中找到可匹配的事實，且模式之間的同一變量能取得統一的約束值。形式化地說，規則

if P1,P2,…Pmthen A1,A2,…An

稱為可滿足的，若存在一個通代σ，使得對每一個模式Pi，在工作存儲器中有一個元素Wi滿足

Piσ=Wii=1,2,3 …m

這里，σ作用在某個模式的結果稱為模式實例，σ作用在整個規則的結果稱為規則實例。在專家系統中，可滿足的規則稱為標志規則。

2、沖突集：由全體規則實例構成的集合稱為沖突集，也稱上程表。免費論文參考網。

3、模式匹配算法的任務是：給定規則庫，根據工作存儲器的當前狀態，通過與規則模式的匹配，把可滿足規則送入沖突集，把不可滿足的規則從沖突集中刪去。

二、Rete算法的依據和基本思想

Rete算法快速匹配的重要依據是：

1、時間冗余性。免費論文參考網。工作存儲器中的內容在推理過程中的變化是緩慢的，即在每個執行周期中，增刪的事實只占很小的比例，因此，受工作存儲器變化而影響的規則也只占很小的比例。由產生式系統的折射性，只要在每個執行周期中記住哪些事實是已經匹配的，需要考慮的就僅僅是修改的事實對匹配過程的影響。

2、結構相似性。許多規則常常包含類似的模式和模式組。

Rete算法的基本思想是：保存過去匹配過程中留下的全部信息，以空間代價來換取產生式系統的執行效率。

三、Rete匹配網絡結構與過程

Rete算法的核心是建立Rete匹配網絡結構，其由模式網絡和連接網絡兩部分構成。其中，模式網絡記錄每一模式各域的測試條件，每一測試條件對應于網絡的一個域結點，每一模式的所有域結點依次連起來，構成模式網絡的一條匹配鏈。

Rete網絡匹配過程由模式網絡上的模式匹配和連接網絡上的部分匹配構成。在模式網絡的機器內部表示中，我們把共享一個父結點的所有結點表示成一條共享鏈。同時，把每一模式匹配鏈中的結點表示成一條下拉鏈，于是，每一結點由共享鏈和下拉鏈指向其后繼結點，模式網絡就是一棵可以使用典型遍歷算法進行測試的二叉樹。

四、智能防火墻Rete算法設計

Rete快速匹配算法，函數Rete設計為:取IP地址、端口號各部分折疊、異或運算后，以Rete長度取模。免費論文參考網。算法如下(無關或部分無關稱為集合A，相關、包含相等和相等的稱為集合B):

1、Addr=sa+da sa:源地址 da:目的地址

2、Port=sp+dp sp:源端口號 dp:目的端口號

int Rete(long addr, int port)

{int addrxor,key；\地址折疊異或

addrxor=(addr&～(～0﹤﹤16))∧((addr﹥﹥16)&～(～0﹤﹤16))；

key=addrxor∧port； \與端口異或

return(key % max)； }\max為Rete表長度

防火墻初始化時，首先從規則集A用該散列函數構造Rete表R為

Void Initialization(RULE-SET A){

FOR(r∈A)DO{ \r為每條規則

idx=Rete(r.addr,r.port)；

R[idx]=&r； \R代表規則集合A

}}

因為Rete表的長度有限，但是如果設計太大會浪費存儲空間，也降低了查找速度，所以免不了會出現沖突。解決沖突的方法是:如果兩條規則經過散列后落到同一位置，則把這兩條規則按照插入順序組成一個鏈表結構。主要算法如下:

if(R[Rete(r.addr,r.port)]=NULL)\R為Rete表,r為規則

R[Rete(r.addr,r.port)]=&r；\沒有沖突，則插入Rete表

Else{J=R[Rete(r.addr,r.port)]；\沖突解決方法

while (j->next!=NULL) {j=j->next；} \插入鏈表末尾

j->next=&r;}

數據包匹配流程：當防火墻收到一個數據包以后，用算法Match查找規則集(A和B)。

Match(IP-Packet p) { \p為數據包

Int idx=Rete(p.addr,p.port) ； \首先用Rete算法查找A類規則

IF (R[idx].addr≧p.addr&& R[idx].port=p.port) \找到匹配規則

return R[idx] ；

Else {int idex I =halfquery(p.addr) ； \利用折半查找索引表

J=L[indexl] ； \L代表規則集合B

While(j!=NULL){\順序匹配找到的規則鏈

IF (Matchrule(p)) return j； \ Matchrule為規則匹配函數

Else j=j->next；

}}

Return(Norulematch)；

}

參考文獻：

[1] 閆麗萍，潘正運. RETE算法的改進與實現.微計算機信息，2006 (36）

[2] 龐偉正，金瑞琪，王成武. 一種規則引擎的實現方法.哈爾濱工程大學學報，2005(03)

篇（2）

中圖分類號：TP311.52

1 引言

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

湯穎曾在《畢業設計立項與選題管理及其支持系統》中提出，采用模糊匹配技術進行學生-題目的自動匹配；潘志方在《一種改進的Ford-Fulkenson算法在選題系統中的應用研究》中將題目與學生的匹配抽象為二分圖的匹配，并采用改進的Ford-Fulkenson算法實現題目與學生的自動匹配。以上兩種方法只考慮了學生與題目之間的最大匹配值，并沒有考慮學生的整體滿意度最優的情況。

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

2 系統功能模塊設計

根據前期的可行性分析，本系統主要進行以下模塊的設計：系統管理員模塊、專業負責人管理模塊、指導教師管理模塊和學生選題模塊。

系統管理員模塊主要負責對系統參數的設置及用戶的管理。主要實現以下功能：

（1）系統設置：對系統標題、畢業生、選題參數設置；

（2）學院及專業設置：完成學院、專業的添加、刪除、修改操作；

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

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

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

專業負責人管理模塊與系統管理員權限相似，但操作的數據只能針對于指定專業，無法瀏覽及操作整個學院的課題及學生信息。最重要的功能是實現題目的審核。

導師管理模塊主要用于選題以及選擇自己選題學生的審核確認。

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

（2）選題管理：選題的增加、修改、刪除以及選題類型的設置；

（3）學生選題查詢及審核。

學生模塊主要實現學生選題的選擇及確認。

（1）學生個人信息的修改；

（2）學生選題及確認信息查詢；

（3）學生留言及咨詢。

3 KM算法在系統中的實現

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

KM算法可以很好地解決選題系統中，題目與學生最優匹配的問題。下面以國際商學院09級本科學生選題為例。

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

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

4 結語

本系統實現了畢業論文選系統工作的各個管理功能，通過實現教師與學生的雙向選擇，使用KM算法，提高選題的質量和效率，為學院充分利用網絡完成畢業論文選題工作提供了便利的平臺。

參考文獻：

[1]湯穎.畢業設計立項與選題管理及支持系統[J].合肥工業大學學報，2006，29（5）.

篇（3）

中圖分類號：TP391.9 文獻標識碼：A 文章編號：1009-3044（2014）02-0305-03

伴隨網絡技術的發展，網絡信息大量增加，涵蓋期刊、會議紀要、論文、學術成果、學術會議論文的大型網絡數據庫應運而生，如萬方數據庫、百度文庫、維普數據庫等，文獻存儲容量近百萬篇。如何有效搜集發現信息，并對信息提取、組織、處理，就需要尋找出高效算法，降低計算復雜度，提高運算效率，以適應文獻資源的迅速擴充[[1]]。

1 文獻資料搜索引擎技術特點

當用戶以關鍵詞查找信息時，搜索引擎會在數據庫中進行搜尋，如果找到與用戶要求內容相符的信息，便采用特殊的算法，根據文獻中關鍵詞的匹配程度，如出現的次數、頻率等計算出各文獻的排名等級，然后根據關聯度高低，按順序將這些資源接返回給用戶。

與網絡搜索引擎不同，因用戶需求為數據資料而非網絡資源，因此文獻檢索主要依據為相關關鍵詞、內容的相關度等，對域名、外鏈等因素考慮較少。可利用關鍵詞匹配算法，計算出各文獻特征值，以特征值作為依據，對檢索文獻排序刪選，滿足用戶需求。為便于理解，該文利用詞頻和位置加權算法計算特征值，采用快速排序算法進行整理輸出，數據庫可高效檢索出與用戶需求匹配程度較高的文獻[[2]]。

2 快速排序算法規則及性能分析

快速排序是由托尼·霍爾于1962年（Tony Hoare）所發展的一種遞歸排序算法，采用分治的思想。在平均狀況下，排序 n 個項目需要Ο（n log n）次比較。

其算法規則可表述為：

3 算法設計與仿真

首先建立包含十五篇文獻的資料庫，根據用戶需求，隨機輸入關鍵詞，在此可將關鍵詞視為子串，對各文獻進行字符串匹配操作。文獻為A串，即目標串，關鍵詞為B串，即模式串。若A串中存在和B相等的子串（ 若干連續的字符組成的子序列） ，則匹配成功，，否則，稱匹配不成功[[3]]。

匹配過程如圖2所示，將模式串設置為滑動窗口。在第一次匹配過程中，第三個字符出現不相同情況，此時根據KMP算法原則，利用已經得到的部分匹配的結果，將模式串窗口向后滑動一段距離后，繼續進行比較[[4]]。

參考文獻：

[1] 張興華.搜索引擎技術及研究[J].現代情報，2002（2）：142.

[2] 黃知義，周寧.幾類搜索引擎的原理剖析、比較研究及發展趨勢探討[J].圖書館學研究，2005（3）：61-62.

[3] 李靜.字符串的模式匹配算法[J].青島化工學院學報，2002（2）：80.

[4] 俞文洋，張連堂，段淑敏.KM P模式匹配算法的研究[J].鄭州輕工業學院報，2007（5）：65.

[5] 黃德才，戚華春.PageRank算法研究[J].計算機工程，2006（2）：145-146.

篇（4）

中圖分類號：TP309

隨著計算機技術的不斷發展，需要處理的數據內容不斷呈現出大量化的特點。近年來，在計算機研究領域內模式匹配問題受到了極大的關注。在串處理系統中，子串在主串中的定位操作是一種重要的過程中，稱之為串的模式匹配。隨著計算機網絡搜索引擎技術的發展、病毒技術的進步以及數據壓縮方面的不斷發展，模式匹配算法在計算機應用系統中得到了廣泛的應用。目前主要的匹配算法有BF算法、KMP算法與一些改進的算法，從方式上，可以分為精確匹配、模糊匹配、并行匹配等。本文重點對KMP算法進行分析，另外對于改進的KMP算法進行研究與展望。

1 簡單的模式匹配算法

現代計算機技術不斷發展，人們的工作、生活與互聯網有著密切的聯系，同時網絡內容也不斷豐富，每一個終端幾乎都有可能會上傳與下載數據，造成網絡上的類似相信也非常多，如何能夠從大量的信息中進行查找同樣的信息，則需要經過一定的算法。[1]這種典型的應用系統將會使用到匹配算法。簡單的模式匹配算法主要是一種查找過程，給出一個特定的字符串P，在一大型的文本中進行查找，從而確定出P是否在大型文本中出現過，如果存在，同時給出相應的出現位置。在以上的算法定義中，為了對數學模式進行簡單描述，進行以下符號定義。模式串為P，需要匹配的大型文本主串為T，模式串的長度為m，需要匹配的大型文本主串長度為n，在模式串中首字符與末字符分別為P1與Pm，而需要匹配的主串文本首字符與末字符分別為T1與Tn。文本字符串T與模式字符串P分別是由字符組成的一種集合，強行搜索模式實質上就是把模式P與文本T進行自左向右的挨個搜索，如果模式字符串P在某一點的匹配失敗，則立即將T向右移動一個字符的位置，繼續從模式字符串P的第一位向右來搜索。[2]這種算法基本上是最符合原理的，但同時它的工作量十分巨大，體現出的效率并不高，需要進行m（n-m+1）次的字母匹配運算，往往給過程浪費大量的時間。現代社會是高效社會，一旦在網絡搜索中速度過慢，用戶將會失去耐心。目前更多的手持設備在應用搜索時一般是即時搜索，對時間的要求較高，運算量太大的低效搜索模式已經不再滿足現代需求。每個網站的用戶數量都在不斷增大，形成的用戶名與密碼都需要進行數據儲存，利用模式匹配法可以對賬戶與密碼進行匹配，從而判斷是否可以登入，否則就進行拒絕，有效提高時間，保護網站利用與用戶隱私。這是模式算法的典型應用，隨著算法的不斷進步，將會在多個網絡領域內得以廣泛應用。[3]

2 KMP算法

KMP算法目前已經經過了多年的發展，最早是由克努特、莫里斯與普照拉特同時發現，是一種改進的字符串匹配算法，在這種算法中，對主串指針回溯進行了消除，利用已經得到的部分匹配結果把模式串右行一段較遠的距離，再次進行比較與匹配，從而使算法的效率得到大幅地提升。這主要是因為在前期的匹配過程經驗總結中，一旦某字符不符合模式串的匹配要求，在附近的一段文本中也將不會出現匹配的對象。[4]

KMP的算法思想是當Ti與Pj匹配完成時，主串的指針i與模式的串指針j將會分別加1，不斷向后面進行再次匹配，如果Ti與Pj匹配不成功時，主串的指針i保持不動，模式的串指針j將不會回到第一個位置，而是回到一個合適的位置，一旦j回到了第一個位置，將有可能會對需要匹配的文本字符進行錯過。主串的指針i保持不動時，算法的關鍵就在于模式的串指針j指回到了哪一個位置。模式的串指針j不可右移太大的距離，避免錯過有效匹配，同時也要右移盡可能地大，以提高匹配效率。在某次字符匹配時，一旦不匹配，模式的前j-1個字符能夠匹配，則在下一次匹配時，可以把模式串向右移動j-s-1個字符位置，從而使P1與Tj-s對齊，需要從P3+1開始進行匹配情況檢查。為了避免遺漏問題，在以上的首字串必須是最長的，自匹配的部分字串是唯一的，與模式自身結構有關。當模式的第j個字條與主串里的該字符進行比較位置時，它的值主要是取決于模式本身，與主串無關。這時關鍵是要選擇模式的適當位置。

3 改進的KMP算法

模式匹配的KMP算法有效地避免了BM算法中頻繁回溯的問題，極大地提高了模式匹配的效率，但這種算法并不是最優秀的。經過長時間的探索與分析，KMP算法中的掃描部分仍然可以進一步改進。[5]

在改進的KMP算法中，當某一次匹配失敗時，i指針不需要進行回溯，而是使用已經匹配到的結果，查看是否對i的調整進行必要性評估，之后再決定與向右滑動的位置模式進行比較。主串指針i的有效變化可以有效提高匹配的效率。在進行第一次匹配結束時，j=6處，無法進行匹配時，i指針將會定為6，j指針為6，當模式串向右移動三個位置時，開始進行第二次的匹配，i的指針為9，而j的指針值為3，也就是說從主串的第九位開始進行比較，i值的不斷增加也就加快了模式匹配的進度，提高了工作效率。

4 利用改進算法進行多次模式匹配

與單模式匹配算法相比，多模式匹配算法的優勢在于一趟遍歷可以對多個模式進行匹配，從而大大提高了匹配效率。對于單模式匹配算法，如果要匹配多個模式，那么有幾個模式就需要幾趟遍歷。當然多模式匹配算法也適用于單模式的情況。在入侵檢測系統中，一條入侵特征可能匹配或部分匹配很多條規則，如果采用單模式匹配，在匹配每條規則時都需要重新運行匹配算法，效率很低。然而，日益增多的網絡攻擊使得入侵檢測的規則數目仍在不斷增長。

在實際的應用中，模式串與主串一般需要多次的匹配，才能找到主串中是否有多次存在相同的子串，如在數據庫中進行查找。[6]通過多次模式的匹配可以實現多個子串在文本中的位置，同時可以進行標記，有利于現代計算機龐大數據量的數理與分析。我國人口眾多，網民數量龐大，姓名與用戶名很可能會出現重復的情況，所以需要提前在數據庫中進行查找，以確定是否可用，另外對匹配但其他特性不符的對象進行排除。

5 結束語

隨著現代計算機技術的不斷發展，越來越多的新技術得以應用與改進。網絡安全發展形勢也要求提高網絡入侵檢測系統的性能。模式匹配的效率問題引起了足夠的重視。通過對傳統的KMP模式匹配算法與其發展狀況進行分析，明確未來發展思路，為其實踐應用奠定理論基礎。

參考文獻：

[1]李桂玲.一種改進的KMP模式匹配算法[J].吉林工程技術師范學院學報，2009（10）：75-77.

[2]楊戰海.KMP模式匹配算法的研究分析[J].計算機與數字工程，2010（05）：38-41.

[3]陳冬文，張帆，王斌，周啟海.模式匹配算法――KMP算法的改進[A].2008中國信息技術與應用學術論壇論文集（一）[C].成都：西南財經大學信息技術應用研究所，2008.

[4]明廷堂.BF與KMP模式匹配算法的實現與應用[J].電腦編程技巧與維護，2013（23）：24-28+34.

[5]范洪博.快速精確字符串匹配算法研究[D].哈爾濱：哈爾濱工程大學，2011.

篇（5）

中圖分類號：TP301文獻標識碼：A文章編號：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

隨著計算機技術和互聯網技術迅猛發展，傳統教育模式發生了變化，越來越多的課程提出了在線考試的需求。計算機可以很好地完成客觀題（如選擇題、判斷題）的判分工作，其判分策略、關鍵技術及其應用實例詳見文獻[1]至文獻[3]。亦即把考生作答的結果和題目標準答案進行精確匹配從而得到考生的得分。文獻[4]提出了一種近似串匹配算法來對文本錄入題的自動評分算法，其本質還是進行文本的比較，與客觀題的判分原理基本是相同的。

計算機自動評分是指利用計算機程序來模擬人工評分的標準和內部過程。對客觀題的評分是通過把試題的標準答案與考生的答案做一個精確比較，并據此作為是否給學生相應的題目分值；對于主觀題，目前一般是讓考生把其作答的結果形成一個文件（答案文件），再通過網絡把考生的答案文件上傳到考試服務器中的專用目錄中，科任教師在考試結束后對考生的答案文件進行人工評判來進行給分；最后把考生客觀題的計算機自動評分結果和主觀題的人工評分結果累加起來作為考生的最終成績。對于客觀題可以完全不要人工干預，而主觀題就必須在人工干預下才能完成。

因此本文就此提出將人工智能的自然語言理解技術（主要是分詞算法）、文本的空間向量模型表示和知識的框架表示內容應用到網絡考試系統中的主觀題的自動評分過程中。

1 文本主觀題自動評分原理

對于在線考試系統來說，其自動評分是在特定范圍內的，不需要讓其理解所有的自然語言，只需要理解標準答案即可。因此，應該使用某種算法使標準答案轉化成機器能夠理解的形式，將考生答案也按照一定的規則轉化成計算機可以理解的形式，然后再將其和標準答案進行匹配并評分。其關鍵是如何將評分規則轉化為可以被機器理解的知識庫。主觀題的自動評分原理如圖1所示。

2 自動分詞算法簡介

2.1 最大匹配分詞算法

匹配分詞法是按照一定的策略將待切分的漢字串與一個“充分大的”機器詞典（如金山詞霸等）中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功（識別出一個詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配。按照不同長度優先匹配的情況，可以分為最大（最長）匹配和最小（最短）匹配。最大匹配分詞法即先確定一個最大的詞的長度，然后從左（正向）或從右（逆向）取該長度的詞串，將詞串與詞典中的詞條匹配，如果沒有該詞則去掉一個字符繼續匹配，以此類推，直到達到匹配或剩下一個單字為止。

2.2 最大概率分詞算法

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

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

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

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

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

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

3 文本矢量特征匹配算法

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

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

4 算法測試及結論

本論文采用oracle作為后臺數據庫管理系統（因為系統所用的詞典數據庫都比較大），基于B/S模式設計了基于文本的主觀題自動評分測試軟件。通過對不同名詞解釋題目（答案長度及復雜度不同）的評測，再將本算法評得的分數與人工評分相比，分數的容差在（－0.5～＋0.5），可以測得其評分的準確度在86.93％。通過實際的數據測試可以看出，答案越復雜，要點越多，評分的準確性越差；相反，要點越少，答案越簡單，評分的準確性越好。而且人工設置關鍵詞和權重也有利有弊，人工設置固然增強了系統的準確程度，但是其前提是設置人必須是有經驗的老師，如果是沒有經驗的老師設置，則給算法增加了人為的誤差。該算法具有一定的實用性，但還有待進一步的完善。

參考文獻：

[1] 華蕊. 自動組卷及評分系統的設計[J]. 中國電化教育.2002,(2):84-85.

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

[3] 李丁. 計算機考試系統中自動評分策略的研究與實現[J]. 廣東廣播電視大學學報,2002,11(4):30-32.

篇（6）

引言

建立城市交通綜合信息平臺，通過對龐大的城市交通網絡中的實時交通信息進行深入分析，為改善城市交通信息服務水平，提高決策科學性，緩解城市交通擁堵提供了基礎。交通綜合信息平臺的數據支撐來源于交通基礎信息的實時采集，科學決策的依據在于數據分析的快速、準確。

GPS浮動車是獲取道路實時車速便捷有效的方法，可以通過車載GPS定位信息獲取道路實時車速及運行狀態（擁堵、暢通、緩行），其作為一種便捷廉價、可操作性高的車速采集手段已經被各城市普遍采用，特別是公交車與出租車安裝車載GPS設備最為常見。通過對公交車及出租車的GPS返回數據與城市道路網的匹配、分析來獲取道路的實時車速，進而實現對道路狀態的有效判斷。因此確保GPS浮動車軌跡點數據與信息平臺電子地圖快速、準確匹配是管理決策的基礎，研究準確適用的GPS浮動車軌跡點數據的地圖匹配算法是非常重要的。

1 GPS數據的地圖匹配原理

地圖匹配（Map-Match）簡稱MM技術，就是利用電子地圖的路網信息和GPS數據來實行對車輛行駛準確位置的確定，它是一種定位誤差修正技術。

浮動車所上報的GPS數據中包含有經緯度等地理信息，但這些GPS坐標只能反映車輛位置情況，而不能與實際路網路段直接相關聯。因此，車輛在路網中行駛的情況，必須要依賴于地圖匹配算法來完成車輛位置信息與路網位置的關聯。

地圖匹配算法的直接目的是將GPS測得的車輛位置或行駛軌跡，與現有的電子地圖道路路段數據進行比較，繼而找到車輛所處的道路，計算出浮動車輛在道路上所處的位置。一般地圖匹配過程有以下幾個步驟：

（1）通過對獲取的GPS數據的預處理及匹配模板的分析、描述，提取出點和道路的軌跡特征。

（2）根據對地圖匹配規則的制定，計算出GPS樣本和匹配模板兩者的相似度、匹配度。

（3）選取待匹配點距離最近或者是軌跡相似度、匹配度最高的道路曲線模板，可更正匹配樣本的位置或軌跡，作為匹配結果[1]。

圖1 地圖匹配原理圖

地圖匹配原理一般可分成兩個過程來表達：即尋找GPS待匹配點最可能歸屬的道路，并將GPS浮動點投影到這條它所歸屬的道路上面。

以上兩個過程的關鍵在于需找GPS待匹配點最可能歸屬的道路，基本的思想即是在GPS點四周一定范圍內搜索所有的可匹配點，然后根據匹配度計算，淘汰匹配度較低的點，選出最優點。并將此最優點作為GPS浮動車車輛的當前行駛路線。這樣，尋找最優點成為算法性能優劣的關鍵所在，如果搜索范圍過大，需對周圍各條道路一一篩選，增加了算法計算量，導致匹配速度緩慢。反之，如果搜索范圍過小，則有可能未能準確尋找到最佳匹配點，出現匹配錯誤，降低匹配的準確率。

2 基于GPS軌跡點的浮動車地圖匹配算法

可實現地圖匹配的算法很多，在GPS數據量極大，且算法應用的場景為實時車速展示，需要選擇一個合適的方法，保證匹配的準確性和匹配速度。因此文章提出的地圖匹配算法是基于GPS點到校正點的匹配，并且利用連續幾個GPS點的軌跡確定結果，最終獲取較為正確的路網匹配結果。

2.1 網格匹配

Step1：計算GPS點所歸屬網格。

當在系統中導入GPS數據信息后，可從這些原始數據中提取出坐標信息。可設為（x，y）。然后對該GPS坐標信息進行可信度檢測，首先取網格劃分中最大和最小的兩個坐標點，其中最大的坐標點位于地圖的右上角，假設為（xm，ym），最小的坐標點則位于地圖的左下角，假設為（xn，yn）。如果待匹配點坐標（x，y）滿足以下條件：

則認為該GPS點在研究坐標范圍之內，轉到下一步計算。

Step2：搜尋所在網格匹配

根據該GPS點的坐標信息，在網格列表中搜尋其所屬的網格。假設網格編號為G0，若

（x，y）∈{G0}

則判定該點位于G0網格內。

在搜尋到所在網格后，將所在網格G0中的所有校正點加入到待匹配集合。但在該匹配中需要注意的是當GPS點與網格邊距離小于1/3時，則需要將其相鄰網格（G1……G8）所包含的校正點一并加入待匹配集合，進行匹配度計算。（見圖2）

2.2 節點匹配

Step1：計算GPS與路段的距離和方向差

在網格匹配中搜尋出的校正點集合被稱為待匹配集合。需要將GPS點與帶匹配集合中的各個校正點進行匹配，找尋出最佳匹配點。

計算GPS點與各待匹配校正點之間的距離。設GPS點坐標為（x，y），GIS校正點坐標為（xr，yr），由于兩點距離較近，兩點接近于平面，則可根據平面距離公式

得出GPS點與各校正點之間的距離d。

計算GPS點與路段各校正點之間的夾角。取GPS數據的角度為？漬0，再與網格內的GIS路段校正點的切線方向角度？漬r（取正北方向為0°）求差值。可得出GPS點與路段方向的夾角α。

Step2：匹配度計算

匹配度是判斷校正點優劣的重要標準，是描述GPS點與一條道路的匹配程度，用實際算法所求得的數值進行量化，匹配度越大，就認為發出這個GPS數據的浮動車越有可能位于這條道路。對于匹配度的計算，主要考慮的是GPS與路段的距離及其與路段的夾角。

圖3 GPS點匹配

Step3：Confidence Point（CP點）判斷

針對GPS浮動車地圖匹配的特殊性，本文提出了Confidence Point判斷。所謂Confidence Point，就是可信點[8]。判斷是否為CP點，主要判斷其所有匹配點是否位于同一路段。

由于浮動車地圖匹配的最終目的是為城市各條道路得到路段平均速度提供起點、終點以及時間信息，而當車輛距離路口（包括城市立交路口、普通平面交叉路口、主輔路的出入口等）比較近時，由于GPS浮動車減速、并線等駕駛行為導致GPS數據中的方向信息等變化較大、準確性降低，使得系統比較難以確定車輛的準確位置。 但是考慮到GPS浮動車地圖匹配的一個最終目的是獲取路況實時信息，因此，如果無論車輛當前在哪條道路上行駛，只要能確定車輛必定通過或者必定離開某個路口，就可以根據GPS浮動車輛的下一個GPS定位數據確定其這一段時間的行駛軌跡。

因此當GPS數據處于路口節點或分合流點附近時，它所對應的匹配點并不在同一路段上，系統將這樣的數據判定為非CP點，作為延遲匹配點，利用行駛路徑進行匹配。反之，若GPS數據所對應的匹配點位于同一路段，則系統將其判定為CP可信點，對其各匹配點進行匹配度計算。

其中對于CP可信點，系統按照step3中匹配度計算中所確定的方法進行匹配度計算。取匹配度最大的點為最佳匹配點。對于非CP點，則轉入下一步。

Step4：延遲匹配

對于上一步所提到的非CP點，并無法通過單一的GPS數據匹配來確定浮動車的確切位置，這時就需要通過相同浮動車的多個GPS數據來聯合判斷車輛的行駛路線軌跡。

圖5 非CP點延遲匹配示意圖

假設某浮動車連續的n個GPS數據組成的序列Pn（n=1，2，3，……，k），滿足以下條件：

（1）P1點為CP點，P2為非CP點，且k小于延遲匹配的允許最大值；（2）Pk為已經確定的CP點，并能按照地圖匹配方法正確尋找到最佳匹配點。

則可利用前后兩個CP點P1和Pk，尋找這相鄰兩個CP點的最短路徑L。再利用最短路徑L對P2，P3，Pn-1進行匹配，去掉不屬于L的匹配點，再取最大匹配度點作為最佳匹配點。

3 結束語

文章所使用的地圖匹配方法通過獲取GPS浮動車數據，利用GPS坐標信息，通過比對電子地圖各條路段的地理信息，將浮動車位置關聯到路網上。

研究表明，該匹配算法具有以下優缺點：

（1）匹配速度快。由于將電子地圖網格化，避免了將GPS數據坐標與地圖中所有節點坐標的一一進行計算，而是僅選取了比較小范圍的節點進行匹配。提高了運算、匹配的效率。

（2）匹配精度較高。由于在匹配方法上采取了多種方法進行聯合使用，針對不同位置的GPS數據點運用不同的匹配方法，保證了每個GPS數據點匹配的準確性。特別是基于連續GPS點軌跡來判斷位置，使得匹配的結果更為準確。

重慶市政府在2011年開展“重慶市交通綜合信息平臺”建設，信息平臺對重慶城區的干路網交通信息進行采集與匯聚。文章的研究依托交通信息平臺的基礎數據，研究成果應用于重慶市主城區路網運行情況的評估與監控，經過實測對比，驗證了該算法的良好精度和適用性。

參考文獻

[1]張其善，吳金培，楊康凱.智能車輛定位導航系統及應用[M].北京：科學出版社，2002.

[2]肖鋒.面向道路交通狀態監測的GPS與GIS數據預處理關鍵技術研究[D].重慶大學碩士畢業論文，2008.

[3]重慶市交通綜合信息平臺試點工程技術報告[R].2012.

[4]孫棣華，等.基于預處理的城市路網拓撲結構構建算法[J].計算機工程與應用，2008（08）.

[5]車莉娜.車輛導航定位中的關鍵技術研究[D].遼寧工程技術大學碩士論文，2008.

[6]Weiliang ZENG， Zhaocheng HE and Xiwei SHE. Data Repair Method for Real Time Urban Link Speed Estimation，ASCE2011.

[7]王華.GIS城市道路最短路徑算法研究[J].測繪科學，2010.

篇（7）

【關鍵詞】 頸動脈;斑點跟蹤;金字塔算法;運動分析;平均絕對差函數

Abstract：The motion information in the carotid ultrasound image can reflect the condition of carotid whether it has hardened， expanded and contracted in the right way. Then it can help doctor to diagnose cardio cerebral vascular diseases together with the carotid intima-medial thickness(CIMT).We used the modified block sum pyramid (MBSP) algorithm to analyze the motion of carotid ultrasound images. The result shows that the modified algorithm effectively reduced the computation while speckle tracking. Besides that， the MBSP algorithm has the same accuracy with the block sum pyramid. The tracking result can assist the doctor to evaluate the disk of cardio cerebral vascular diseases to a certain degree.

Key words：Carotid; Speckle tracking; Block sum pyramid; Motion analysis; Mean absolute difference

1 引 言

心腦血管疾病與頸動脈內中膜厚度及其運動特征等有著密切的相關性[1]。對于超聲波圖像而言，可以通過斑點跟蹤的方法獲得運動信息。斑點作為噪聲不可避免地存在于超聲波圖像中。雖然斑點噪聲影響超聲波圖像質量，但是根據斑點噪聲的形成原理，可以通過跟蹤斑點來獲取圖像中相關目標的運動信息。為研究組織的運動特征和彈性信息，進而輔助評估心腦血管疾病提供了一種可能。斑點跟蹤算法一般包括兩個方面：匹配和搜索。匹配的準則有許多種，常用的準則有歸一化相關函數(NCCF)，平均均方誤差函數(MSD)以及平均絕對差函數(MAD)等。因MAD不涉及乘法等復雜運算，所以較為常用，本研究也采用該匹配準則。搜索方法也有好多種，有全搜索法[2]，十字搜索法[3]，菱形搜索法[4]等。此外，在這些算法基礎上發展出了許多快速算法，如金字塔算法[5]，連續淘汰法[6]，改進的自適應2BIT變換法[7]等。臨床實踐中醫生除了用肉眼定性地去觀察頸動脈的運動特征，有時需要定量測量出感興趣的頸動脈某一目標的運動信息(如：短軸切面輪廓在一個心動周期內收縮和擴張的運動狀況)。這樣就能夠更加可靠地評估心腦血管疾病和風險。由于輔助診斷對運動跟蹤的實時性要求不是很高，而對運動跟蹤的準確性要求較高。故我們選擇能達到全局最優的全搜索法和金字塔快速匹配算法的組合進行斑點運動跟蹤，并且對金字塔快速匹配算法進行了改進，將其應用于頸動脈運動分析，高效準確地跟蹤出目標興趣點運動的相關信息。

2 原理與方法

2.1 金字塔塊匹配算法

設有塊X和Y，塊大小均為：2M×2M，對塊X和Y均建立 M+1層的金字塔。從塔頂往下依次為第0，1，…，M層。X，Y的金字塔的第m 層分別記為Xm，Ym。第m-1層和第m層關系如方程(1)所示：

Xm-1(i，j)=Xm(2i-1，2j-1)+

Xm(2i-1，2j)+Xm(2i，2j-1)+Xm(2i，2j)(1)

令：MADm(X，Y)=∑2mi=1∑2mj=1|Xm(i，j)-Ym(i，j)|(2)

可以得出結論(3)：

MAD0(X，Y)≤MAD1(X，Y)≤MAD2(X，Y)…≤MADm(X，Y)…≤MADm(X，Y)(3)

兩個塊在生成了各自的金字塔之后，從頂層往下逐層計算MADm(X，Y)。如果發現其大于或者等于最新的MADmin時，說明本候選塊一定不是最優塊，舍棄該候選塊繼續搜索下一個候選塊，如果比較到最底層，仍然比最新的MADmin還小時，將MADmin更新為當前候選塊與參考塊的MADm(X，Y)。直到所有的候選塊均搜索完后，最小的MADmin的候選塊相對于參考塊的偏移量即為所要求解的運動向量。 金字塔匹配算法就是通過盡快地舍棄那些不是最優的候選塊而減少運算量的。雖然建立金字塔會增加額外的計算量，但是由于大部分的塊在比較時就被舍棄了，所以總的運算量還是大幅地減少。

2.2 改進的金字塔匹配算法

金字塔塊匹配算法從頂層開始往下逐層比較時，層與層間的MAD值相差很大。當層數較大時，最后一層與倒數第二層的MAD值相差更大，因此，比較時仍有不少的計算冗余。為此，希望在現在的金字塔基礎上不改變運算量，在層與層之間新增一些閾值，能夠盡早地舍棄那些不是最優的塊。為了敘述方便，以下討論均以在最后一層(第M層)與倒數第二層(第M-1層)之間增加閾值為例。

兩個要比較的塊分別記為X，Y，塊X和Y的金字塔的第M-1層分別記為：XM-1，YM-1。設SM-1為第M-1層塔的所有像素點空間。將XM-1，YM-1按照相同的方式均分割為N個區域：S1M-1，S2M-1，S3M-1，SkM-1，…，SNM-1，1≤k≤N，見圖1。具體的分割方法還需要根據實際情況進行合理的選擇。分割出的N個區域要滿足以下兩個約束關系：

∑Nk=1SM-1k=SM-1(4)

SM-1k∩SM-1l=，1≤k≠l≤N(5)

圖1 像素空間分割方法

Fig 1 Pixels partition method

圖2 實驗所采取的分割方法

Fig 2 Experiment′s method

同時對塊X，Y的金字塔的第M層也劃分為N個區域SM1，SM2，SM3，SMk，…，SMN，1≤k≤N。也要滿足約束關系：

∑Nk=1SMk=SM和SMk∩SMl=，1≤k≠l≤N。

SM-1k區域中的每一個點對應于SMk區域中的4個點，此對應關系和構建金字塔時從M層到M-1層的4個點累加成1個點的對應關系一致。

構造如下函數表達式：(0≤n≤N)

MADM-1n(X，Y)=MADM-1(X，Y)-∑nk=1∑(i，j)∈SM-1k

|XM-1(i，j)YM-1(i，j)|+∑nk=1∑(i，j)∈SMk |XM(i，j)YM(i，j)|(6)

根據層間區域關系式(1)，上式又可以寫成(7)式：

MADM-1n(X，Y)=MADM-1(X，Y)-f(n)(7)

其中f(n)可寫成(8)式:

f(n)=∑nk=1∑(i，j)∈SM-1k|XM-1(i，j)YM-1(i，j)|-

[|XM(2i-1，2j-1)YM(2i-1，2j-1)|+

|XM(2i-1，2j)YM(2i-1，2j)|+

|XM(2i，2j-1)YM(2i，2j-1)|+

|XM(2i，2j)YM(2i，2j)|](8)

又據三角不等式及上下層點的對應關系知：

f(n)≤0，且f(n)隨著n的增大單調遞減，據此得出(9)、(10)、(11)的3個結論：

MADM-1(X，Y)=MADM-10(X，Y)(9)

MADM-1N(X，Y)=MADM(X，Y)(10)

MADM-10(X，Y)≤MADM-11(X，Y)

≤…MADM-1n(X，Y)≤…MADM-1N(X，Y)(11)

如果將SM-1像素空間一列一列依次從左往右分割時，所得到的有關結論則和文獻[8]是一致的。文獻[8]中所提到的逐行更新算法可看作是本研究改進算法的特例。現將改進的金字塔匹配算法(以在兩幀中跟蹤一個興趣點為例)歸納如下：

記前后兩幀圖像分別為fi(x，y)，fi+1(x，y)，被跟蹤點坐標為(a，b)，前一幀圖像點(a，b)所對應的塊稱為參考塊，搜索范圍為A。

(1)計算相對于參考塊運動位移為(0，0)的候選塊與參考塊兩者的MAD值作為MADmin，并且確定后一幀圖像中的起始候選塊。MAD計算公式如(12)式所示：

MADmin=∑2M-1-1x=-2M-1 ∑2M-1-1y=-2M-1|fi(a+x，b+y)

-fi+1(a+x，b+y)|(12)

(2)依據金字塔算法構建當前候選塊和參考塊各自的金字塔。金字塔總共假設有M+1層。沿金字塔至上而下逐層進行比較，因為這里只考慮在M-1層和M層間新增閾值，所以前M-1層的比較和原金字塔塊匹配算法一樣。當M-1層比較完后，發現MADM-1(X，Y)仍然小于最新的MADmin。此時則需要按照構造函數表達式生成一個新的中間閾值，再進行比較，其間發現新生成的閾值大于或者等于MADmin時，舍棄，直接進入步驟(3)進行下一個候選塊的匹配。否則一直進行到最后一層為止。如果其結果仍然小于MADmin時，更新MADmin。

(3)按照選取的搜索算法(如全搜索法)，確認下一點被候選點及相應的候選塊。重復步驟(2)，直到A所有需要搜索的點搜索完為止。

(4)最后，對應于MADmin值最小的候選塊即為最優候選塊，其相對于參考塊的偏移量，即為所要跟蹤的運動矢量。

2.3 利用MBSP算法分析頸動脈圖像

(1)取頸動脈短軸切面一個心動周期的圖像序列。在第一幀圖像中，沿頸動脈短軸輪廓，手動大致均勻地選取出若干個興趣點，興趣點應盡量選取在整個運動序列圖像中亮度較為平穩且肉眼觀察較為明顯的斑點噪聲顆粒。

(2)利用改進的金字塔跟蹤算法(MBSP)逐幀地跟蹤所有興趣點，得到各個興趣點在各幀中的運動矢量，再將各幀上各點的運動矢量按照適合人眼觀看的比例顯示在各幀圖像上。最后以動態的方式播放附有運動矢量的頸動脈圖像序列，醫生可以根據播放視頻中的運動矢量定性地掌握興趣點運動大小、方向、扭轉、是否出現異常等情況，做出一些如是否可能出現斑塊硬化等初步診斷。

(3)最后給出各個興趣點的收縮擴張曲線，每條曲線給出每個點隨時間的運動速度變化。設第j幀圖像中跟蹤到的N個點的分別為坐標(X1，Y1)，…，(Xi，Yi)，…，(XN，YN)。其均值為(X，Y)。記Vi=(Xi，Yi)-(X，Y)，1

3 實驗與結果

3.1 實驗結果

實驗數據由合肥105醫院超聲科提供，為一個心動周期的頸動脈短軸切片序列圖像，共25幀。第1、11、22幀圖像分別見圖3、4、5。圖3中小白框即為我們要跟蹤的6個興趣點，左上角為1號點，按順時針依次排列。為了表述方便，這里只選取了6個興趣點為例。

分別用BSP和MBSP算法對該頸動脈序列圖像進行斑點運動跟蹤，其中MBSP算法在第3層和第4層增加了3個新的閾值。將第3層的像素空間從左到右依次分割成4個相同的區域，見圖2。實驗中塊大小取為16×16，搜索范圍為8×8。圖4附上了第11幀圖像上各興趣點的運動矢量圖，兩個算法跟蹤出來的結果一樣。圖6給出了各個興趣點(從左往右，從上至下依次為1到6)隨時間變化的擴張收縮運動速度圖。從圖中我們可以看出，興趣點2、3、4的運動表現出較為一致的運動規律，在一個心動周期內經歷一個明顯的擴張和之后的收縮過程。但是觀察興趣點1、5、6的運動速度曲線，發現其運動起伏相對來說沒有這些規律，從而可以認為1、5、6附近區域可能出現一些病變。這和醫生的診斷結果：本試驗者頸動脈左下部區域內膜形成了較為明顯的斑塊，而斑塊區域收縮運動常出現紊亂是相互吻合的。

3.2 性能分析

(1)準確性。分析改進后的算法和改進前的金字塔匹配算法(BSP)，容易得出前后算法運動跟蹤結果應該是一致的，差異只在于計算量上。實際跟蹤的結果也證明了這一點。圖7、8給出了前后兩種算法的跟蹤興趣點1的運動軌跡圖，圖中橫軸、縱軸分別對應于圖像的X軸和Y軸坐標軸。

(2)效率。表1給出了改進前后算法在上述實驗過程中需要計算的各MAD值統計次數。計算第m層的MADm值所需要運算量(含加減法及絕對值)可以公式化[9]為：3.22m-1，計算MADmn運算量約為：5n·(3·22m+2-1)/16。以第4層為例，如果直接采用表1 金字塔算法改進前后各MAD次數

原來的金字塔算法，需要計算總次數為821 457;但采用改進后的算法需要的計算量僅為721 747。可見因為第3層與第4層3個新增閾值的引入，第4層判決過程的總體運算就減少12.11%，可以考慮將區域進行更細劃分，但是要權衡因為閾值增加而造成的比較運算量。如果在第3層等層也引入同樣機制的話，運算量將進一步減少。

4 總結

本研究將改進后的金字塔匹配算法應用于斑點運動跟蹤，實驗結果表明該算法能準確而更加有效地跟蹤出運動矢量。并且將該方法應用于頸動脈運動分析，結合頸動脈的自身特點，給出有利于輔助醫生診斷的擴張與收縮曲線等依據，為頸動脈的進一步分析奠定了一定基礎。

參考文獻

[1]胡瑋，張軍，孔國喜，等. 超聲檢測頸內動脈內-中膜厚度及其形態結構與相關心腦血管疾病的關系[J]. 第四軍醫大學學報 ，2007，28(15):1431-1433.

[2]Brünig M， Niehsen W. Fast full-search block matching[J]. IEEE Trans Circuits Syst Video Technol，2001，11(2): 241-247.

[3]Ghanbari M. The cross-search algorithm for motion estimation[J]. IEEE Trans Commun，1990， 38(7): 950-953.

[4]Zhu S，Ma K-K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans Image Processing，2000，9(2):287-290.

[5]Lee C H， Chen L H. A fast motion estimation algorithm based on the block sum pyramid [J]. IEEE Trans Image Processing， 1997，6(11):1587-1591.

[6]Li W， Salari E. Successive elimination algorithm for motion estimation [J]. IEEE Trans Image processing， 1995，4(1): 105-107.

篇（8）

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

影像匹配實際上就是兩幅（或者多幅）影像之間識別同名點，它是計算機視覺及數字攝影測量的核心問題。我們知道要匹配的點的同名像點肯定在其同名核線上。在進行最小二乘影像匹配之前，需要先進行粗匹配。然后在粗匹配的基礎上用最小二乘法進行精匹配。我們這次討論的是利用一維搜索的方法來進行粗匹配。這就是利用同名核線來進行同名像點的粗匹配。這相對于二維匹配來說速度更快。

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

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

根據前邊的共線方程，同一攝站點攝取的水平像片與傾斜像片，其水平和傾斜像片的坐標之間的關系為：

(1-1-1)

(1-1-2)

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

（1-1-3）

其中：

e3=d3

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

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

(1-1-4)

(1-1-5)

其中， ， ，… 右方像片的對于單獨像對像空間輔助坐標的角方位元素的函數，由此可得右片上的同名核線。

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

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

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

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

1.3數字影像匹配的基本算法

本論文講述的相關系數法主要是對于一維影像相關的。

如圖1-3-1所示是一維影像相關的目標區和搜索區（這里取m=n）。設g代表目標區內的點組的灰度值，g’代表搜索區內相應點組的灰度值，則每個點組共取得了n個點的灰度值的均值為

圖1-3-1一維相關目標和搜索區域

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

兩個點組的方差 ， 分別為：

， （1-3-2）

兩個點組的協方差 為：

（1-3-3）

則兩個點組的相關系數 為：

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

在搜索區內沿核線尋找同名像點，每次移動一個像素，按照（1-3-4）來依次相關系數 ，取其中的最大的數值，其對應的相關窗口的中心像素就被認為是目標點的同名像點。

1.4用相關系數的拋物線擬合來提高相關精度

為了把同名點求的更為準確一些，可以把相關系數的最大點i點左右若干點（一般取左右個兩個點）聯系起來，從而將其函數的最大值k處的作為尋求的同名點的位置，結果會更好一些。

圖1-4-1拋物線擬合

如圖1-4-1所示設有相鄰像元素系處的5個相關系數，用一個二次拋物線方程式來擬合，取用的拋物線方程，代表相應S位置處灰度的數值。

（1-4-1）

式中的參數A，B，C用間接平差方法求的。此時拋物線頂點k處的位置為：

（1-4-2）

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

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

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

在本次僅僅考慮相對位移的一維最小二乘影像相關。在一維影像相關中是在傾斜影像相對應的水平影像坐標系中沿x軸方向尋求同名點，若在最小二乘算法中把搜索區像點移動的位移量作為一個幾何參數引入，就可以直接解算像點的位移。

設有兩個一維灰度函數 ， ，除了隨機噪聲 ， 外， 相對于 存在位移量 。如圖4-3-1所示，則

（2-1-1）

則（2-1-2）

圖 2-1-1 僅考慮相對位移的一維最小二乘影像相關

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

（2-1-3）

對離散的數字影像，灰度函數的導數 可以由差分 代替，即

（2-1-4）

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

（2-1-5）

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

（2-1-6）

因為解算都是線性化的結果得到的，因此，解算需要迭代進行。解得 后，對 進行重新采樣，各迭代計算時，系數 以及常數項 均采用重新采樣后的灰度值進行計算。

2.2計算最佳的匹配點位

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

（2-2-1）

以它作為目標點坐標，它的同名點坐標可以由最小二乘法影像匹配所求得的幾何變換參數求得；

（2-2-2）

隨著以最小二乘法為基礎的高精度數字影像匹配算法的發展，為了近一步提高起可靠性與精度，攝影測量工作者進而有提出了各種帶有約束條件的最小二乘影像匹配的算法。例如，附帶有共線條件的最小二乘相關以及與VLL法相結合的最小二乘影像匹配方法都得到了廣泛的應用和研究。

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

篇（9）

一、引言

指紋自動識別技術是通過計算機實現的身份識別手段，也是當今應用最為廣泛的生物特征識別技術之一。采用指紋識別技術進行身份驗證是安全可靠的系統，它可以取代傳統的基于密碼、鑰匙和證件的安全系統，而且不需記憶密碼，無需攜帶證件，指紋就是身份證明。無數的研究單位和公司企業都積極從事自動指紋識別算法的研究和產品開發，現在國內外指紋識別大都采用基于細節特征點的指紋識別技術，即采用基于圖像處理的指紋識別算法，但有些算法由于指紋圖像的噪音、皮膚彈性引起的非線性形變等多方面因素，導致在識別過程中出現誤差，影響識別率等。

二、研究現狀

在國內，中國科學院自動化研究所人工智能實驗室在指紋識別技術研究方面取得了大量成果，它們的產品“Finger pass嵌入式指紋識別系統”獲國家信息產業部信息產業重人技術發明榮譽證書，“基于混合匹配的指紋識別系統與應用”曾獲得國家科技進步二等獎，并在國內外重要學術刊物上發表多篇關于指紋的科研論文。

國外自動指紋識別技術的研究開發起步比國內早，到目前為止也已經取得了很多優秀成果，它們的技術和產品整體上都領先于國內。比較有代表性的“指紋研究組織”是南加利福利亞洲指紋聯合會，它是一個非盈利組織，成立于1937年，目前擁有超過350個成員單位，該組織旨在推動指紋識別技術及其相應產品的研究、交流等。由國際模式識別協會組織的國際指紋識別算法競賽“FVC2000”、“FVC2002”、“FVC2004”吸引了眾多國際國內的高校、研究組織、企業等參加，這些競賽都非常具有影響力，推動了指紋識別技術的研究和應用發展。

三、指紋預處理

在指紋識別過程中，輸入的指紋圖像由于各種原因的影響，是一幅含噪聲較多的灰度圖像，預處理的目的就是去除圖像中的噪聲，使圖像畫面清晰，邊緣明顯，把它變成一幅清晰的點線圖，以便于提取正確的指紋特征。指紋圖像預處理環節在整個指紋識別系統中具有重要的地位和作用，它的好壞直接影響著指紋識別的效果。預處理一般分為四步進行：指紋圖像的規格化、指紋增強、二值化和細化。

四、指紋圖像的特征

指紋圖像的結構比較復雜，而且屬于個人隱私，所以在一般情況下，指紋圖像是用數字化的形式存儲的，然而數字化存儲信息量大，很難找到準確的指紋信息，因此指紋識別具有重大的意義。指紋識別算法是根據指紋圖像中一些不同的特征來實現指紋的匹配，根據不同特征可以將指紋圖像分為：總體特征和局部特征。

總體特征：指紋圖像中存在一些清晰明了的特征，可以用肉眼直接觀察到，將這一類特征稱為總體特征，例如：紋型，模型區，核心點，三角點，紋數。

局部特征：指紋圖像上節點的特征，而節點是指紋圖像中具有某種特征的點，又稱為特征點。一般來說，有些指紋會存在相同的總體特征，但絕對找不到相同的局部特征，即相同的特征點。所以在指紋識別過程中就是要尋找這些特征點，這些特征點往往出現在中斷處、分叉處及轉折處。

五、指紋特征匹配

人們對指紋匹配做了很多研究，提出了許多匹配算法，主要可分為兩類：一類是基于圖形的匹配方式，包括點模式匹配和基于圖論的方法；另一類是采用人工神經網絡的方法。圖形匹配是針對紋線幾何形狀及其特征點拓撲結構的匹配方式，它的原理是基于相似變換的方法把兩個特征點集中的相對應點匹配起來，這些相似變換可以是平移變換、旋轉變換、伸縮變換等線性變換，可以在一定程度內允許少量偽特征點的存在、真正特征點的丟失以及輕微的特征點定位偏差，且對圖像的平移和旋轉也不敏感。但這種方法有兩點不足：一是匹配速度比較慢；二是對指紋圖像的質量要求比較高，低質量的圖像匹配效果不佳。本文采用概率神經網絡識別的模型進行網絡拓撲。在情報不完全的情況下，對未知部分進行主觀概率估計，然后用貝葉斯公式對其進行修正，最后結合期望值和修正概率做出最優決策。

六、小結

本文通過介紹混合神經網絡相關知識，分析了自動指紋識別系統的研究現狀和問題，按照指紋預處理、指紋特征提取和指紋特征匹配的研究過程，在現有的各種指紋處理算法的基礎上，對它們進行了優化改進，研究了混合神經網絡在自動指紋識別系統中的應用。

參考文獻：

[1] 張瑩，于寶。基于ARM9的指紋匹配算法[J]。計算機與數字工程，2013，5。

[2] 李娟。基于特征描述子的指紋算法研究[D]，西安電子科技大學，2012.

[3] 王啟亮。指紋圖像增強算法研究[D]， 太原科技大學，2013.

[4] 王行甫，覃啟賢，程用遠，侯成龍。一種改進的徑向基神經網絡預測算法[J]。計算機系統應用，2012，8。

[5]殷芳璽。嵌入式指紋識別應用系統與算法研究[D]， 華中科技大學，2012.

[6]車永剛，肖春雨，雷聲，孫巍。基于環形BP神經網絡的指紋匹配算法[J]。長江大學學報，2013，10（1）。

篇（10）

中圖分類號：TP391.41文獻標識碼：A文章編號：1007-9599 (2011) 16-0000-01

Comparative Study of Ddigital Image Copy Paste Tamper Forensics Technology

Han Min,Sun Jinguo

(Chinese People's Public Security University,Beijing102623,China)

Abstract:This article describes several algorithms aiming at a common copy-paste forgery in the research field of digital image forensics,compared?the performance of?various methods.Different of kinds of tamper detection methods have been analyzed and discussed.It also prospects the future of copy-paste forgery in the research field of digital image forensics.

Keywords:Digital image forensics;Image area copy paste tamper

一、引言

近年來隨著電子技術的發展傳統的“膠卷相機”已經幾乎被數碼相機所代替，這為人們省去了很多傳統相機使用上的不變，但伴隨著數字圖像處理軟件的發展，數字圖像的非法篡改給人們的生活以及社會帶來很多負面的影響，數字媒體的信息安全無法得到保障。復制粘貼篡改是一種常見的篡改手法，它利用同幅圖片內各種統計參數比較相近，從一個區域復制一個圖塊粘貼到另一區域上，以達到掩蓋圖像真實內容的目的。

二、數字圖像被動取證技術

數字圖像被動取證技術，要求只給出待檢測圖像就可以鑒別真偽，即在不依賴任何預簽名提取或預嵌入信息的前提下，對圖像內容的真偽和來源進行鑒別和取證的技術，因此這類取證技術也叫數字圖像盲取證技術。

數字圖像被動取證技術實現的可行性基于這樣一個事實：任何來源的數字圖像都有自身的統計特征，而任何對數字圖像的篡改都會不可避免地引起圖像統計特征上的變化。因此，可以通過檢測圖像統計特征的變化，來判斷圖像的原始性、真實性和完整性。

三、取證算法

目前的取證算法大體上可以分為兩類，即基于單個像素的窮舉搜索和基于圖像塊的檢測方法。塊匹配算法共同的特點就是對輸入的圖像數據進行分塊處理。得到這些塊之后，從這些塊中提取相應的特征值構成特征向量，不同的基于塊匹配的算法的實質區別就在于選取的特征值各不相同。下面就各種方法進行比較：

（一）窮舉搜索。基于單個像素點的窮舉法原理很簡單，但計算復雜度很高，將之應用于大幅圖像的篡改檢測顯然是不可行的，與此同時，此算法也不能夠抵抗外來的一些干擾操作，如加噪、模糊等。算法本身受條件的約束性較強。一般我們只用于對較小尺寸的篡改圖像的檢測。

（二）簡單塊匹配。最基本的塊匹配檢測算法是將得到的b2大小的塊展開，每個方形塊按行優先順序被展為一行，存入一個矩陣中，這樣所有的行向量組成了一個二維矩陣X，其中列數為b2，行數為（Mb+1）（Nb+1）。為了減少算法的計算量，按照字典排序的方法對X陣中的行進行排列。最后根據判斷是否存在等同的行向量來確定篡改結果。這種算法在圖像遭到了復制粘貼篡改后沒用進行其他篡改的情況下顯示出了良好的性能，但是當篡改圖像經過如壓縮等后續操作時，檢測的正確率明顯降低，這是由于塊與塊之間不再是精確的相似，檢測效果大打折扣。

Fridrich等人對此進行了改進，先對圖像進行塊離散余弦變換（BDCT）變換，采取經過量化后各塊的BDCT系數進行對比分析。由于是在DCT域上做分析，算法具有一定的魯棒性。但是當處理的圖像比較大時，由于計算量太大，往往需要很長的時間來實現篡改定位，這個時間很可能無法令人接受。

駱偉祺等人提出了一種魯棒的檢測算法，這種算法也是基于圖像塊匹配的。假定問題圖像為彩色圖像（大小為MxN），首先對其進行分塊處理，分塊的方式同前面一樣，在得到了（M-b+1）x（N-b+1）個圖像塊之后，對每個圖像塊提取可以代表其內容的七個特征值，并以向量的形式來表示，前三個分量a1、a2、a3分別是b2大小的彩色圖像塊RGB通道的均值。若為灰度圖，只需記錄像素點的灰度值即可，a4、a5、a6、a7則是由圖像塊內各像素點的亮度分量Y組成的陣列經過四種分解方式整合處理后得到的特征。此算法具有一定的魯棒性能，能夠抵抗一定程度的后處理操作，如模糊、壓縮等。但如果被復制的區域發生了形變，則容易造成誤判，甚至失效。

（三）基于不變矩的檢測算法。不變矩方法是一種經典的特征提取方法，目前已經廣泛應用于圖像分析與模式識別領域中。Hu提出的7個矩不變量，不但具有平移不變性，而且還具有旋轉不變性，適合用于表示圖像的特征。但Hu矩的方法對模糊和加噪操作沒有明顯效果。

Zernike矩是一組正交矩，也具有旋轉不變性，即旋轉目標并不改變其模值。由于Zernike矩能構造出任意高階矩，而高階矩包含更多的圖像信息，所以Zernike矩的識別效果優于其他方法。何坤等人提出了一種方法，將尺寸較大的篡改圖像運用小波變換得到低頻子圖像，再把低頻子圖像分割為圖像子塊，對其子塊序列圖像分別進行Zernike矩分析判斷是否存在復制篡改，該方法克服了噪聲和幾何變換對取證的影響。

（四）基于SVD的檢測算法。奇異值分解（SVD），是一種圖像特征分析方法。它的目的在于消除圖像數據各分量間相關性，是基于信號二階統計特性的一種方法。國防科技大學吳瓊等人提出了一種基于SVD的圖像復制區域檢測算法。利用奇異值分解變換來處理圖像塊數據，并對圖像塊進行相似性匹配檢驗。這種方法對圖像羽化或邊緣模糊等處理具有魯棒性。

四、結語

目前主流算法對于相對簡單的復制粘貼篡改檢測效果較好，但偽造者為了使篡改圖像更加可信，除了采用簡單的平移、旋轉外，還可能會根據實際情況對篡改內容進行縮放、模糊等操作，這樣傳統的塊匹配算法將會失效。因此，在保證算法健壯性與檢測準確率的前提下，我們要設計出能夠同時抵抗平移、旋轉、縮放、模糊等各種操作的取證算法，這是我們今后努力的方向。

參考文獻：

[1]周琳娜.王東明數字圖像取證技術[M].北京:北京郵電大學出版社,2008:69-70

篇（11）

 

1 緒論

圖像拼接技術有悠久的研究歷史。早期用于航空遙感照片合成，在20世紀90年代Heung——Yeung Shum研究了同心圓拼圖(柱面全景圖)， 20世紀90年代中期，微軟研究院的Szeliski教授提出基于運動的全景圖像拼接模型，將8參數減低為4參數，2003年M.Brown發表了全自動的圖像拼接算法的文章，使用捆綁調整技術，同時，魚眼鏡頭拍攝圖像生成球面全景圖的繪制技術也得到廣泛研究。

2 全景圖像拼接技術的概述

2.1 全景圖的模式分類

全景圖根據圖像投影方式的不同，存在幾種全景圖像：一種是球面全景圖像，一種是多面體全景圖像，還有一種是最常用的柱面全景圖像。柱面全景處理起來比球面全景與多面體全景簡單得多，因而應用面比較廣。

2.2 全景圖的生成流程

全景圖的聲稱流程如下：圖像的采集，圖像的預處理，圖像的變換，圖像匹配，圖像的平滑處理。

3 基于特征匹配的柱面全景圖拼接技術的研究

3.1 原始圖像的采集和幾何校正

3.1.1 拍攝方法和原則

照相機拍攝時一般有三種情況：

1.旋轉照相機拍攝

在這種情況下，放置照相機的三腳架在拍攝過程中一直在同一位置。照相機繞垂直軸旋轉，每旋轉一定的角度，拍攝一張照片。拍攝得到一系列照片中相鄰兩張必須有部分重疊。建議相鄰圖像之間重疊比例達到50%。重疊比例越大，拼接就越容易。

2.平移照相機拍攝

平移照相機指的是照相機在一個平行于成像平面的方向上平移。這種情況的缺點：拍攝的相片在一個平面上，拍攝的三維感覺不如旋轉拍攝的。科技論文。

3.手持照相機拍攝

這種方法比較容易做到，手持照相機原地旋轉拍攝。但是，拼接手持照相機拍攝的照片是很困難的，因為在拍攝過程中，照相機的運動非常復雜。可以增加重疊比例，使照相機旋轉角度、平移減小，因而減小相鄰圖像之間的不連續程度。

用照相機拍攝全景圖像，要取得較好的效果，必須注意以下幾個方面的原則：

3.2 圖像的變換

將一幅圖像與另一幅圖像匹配，常需要對一幅圖像進行一系列的變換，這些變換可分為剛體變換、仿射變換、投影變換和非線性變換。

3.3 圖像的匹配

3.3.1圖像拼接算法的原理

一般情況下，經過柱面投影變換得到的具有重疊區域的柱面全景圖中相鄰的兩幅待拼接圖像間的重疊[2]范圍大約在30%-50%之間。為了減少在特征區域提取時候的盲目性，我們可以先對灰度圖像進行圖像輪廓的提取，盡量的讓選擇的特征區域包含獨特的信息，容易識別。

在圖像匹配過程中，希望匹配點要準確，即關峰尖銳，定位精度高，因此在實驗過程中用邊緣檢測的方法提取圖像的邊緣從而使圖像的輪廓更為清晰，這樣有利于提高匹配的精度和降低偽匹配的可能性。

3.3.2 基于特征區域的提取和匹配算法的實現

本文采用Moravec[3]算子進行特征區域的提取，窗口的大小可以采用55到2121。窗口越大，抗噪聲能力越強，同時運算量也越大。

特征區域的匹配過程步驟如下：

1.將匹配圖像重疊部分的像素灰度值和位置信息讀入數據矩陣B，矩陣B讀入的是匹配圖像重疊部分的數據。

2.設置一個或者多個二維循環，通過對循環條件的設置或者分段設置循環，使搜索路徑可以沿著預處理之后提取的輪廓邊沿進行，將整個圖像的重疊區域全部搜索一遍。科技論文。

3.沿著搜索的路徑提取矩陣B的55，并且對矩陣內部的元素進行運算，分別計算該矩陣和單位矩陣的元素的均方差和灰度差的絕對值之和，分別把它們賦給兩個變量。

4.將記錄的當時搜索區域和單位矩陣的均方差和灰度差的絕對值之和跟之前的記錄值作比較（記錄值的初值的均方差為0，灰度值的絕對值之和為10），記錄均方差的最大值和灰度值的絕對值之和的最小值，并且分別記錄它們的坐標位置。科技論文。

5.搜索矩陣下移，再次重復步驟2和步驟3。

6.搜索結束，就得到了在矩陣B中令均方差最小且灰度值的絕對值之和最大的區域，記錄該區域的位置和中心點的坐標位置。

在本課題的實現過程中，待拼接的圖像已經經過了預處理和輪廓提取，所以在拼接的過程中，只需要將算子的中心沿著重疊部分圖像的輪廓進行就可以了。

3.4圖像的平滑處理

在拍攝柱面全景圖時，周圍環境和相機本身引起的最大問題就是相鄰圖像之間的光照變化較大，會出現帶狀痕，為了消除這種拼接區域帶狀痕影響，提出了一種直方圖處理方法：

1.對于24位色圖，首先將RGB圖像轉換成HIS類型圖像，針對其I分量進行處理，等同于對灰度圖像的灰度值進行處理。

2.將兩幅圖像的1/3公共部分作為重疊區域，注意要保證兩個重疊區域像素數目一致。

3.分別計算左、右兩邊重疊區域的I分量或灰度圖像灰度值的和sum1與sum2。

4.Differ=sum1/sum2，將圖像2的每一個像素的I分量或者灰度圖像2的每一個像素的值與參數Differ相乘加權。這樣做的目的是將兩幅圖像的亮度均值統一，使得重疊區域在拼接時能夠平滑過渡。

4 總結與展望

隨著虛擬現實技術的不斷發展，虛擬現實技術開始走向大眾化，并應用于網上購物、網上旅游、網上教育和在線游戲等領域，虛擬現實系統將會成為未來世界一個不可缺少的重要組成部分。

【參考文獻】

[1]王玉珍.基于特征區域的圖像拼接技術.蘭州大學碩士學位論文，2001：

3-10

[2]蘭培真,馬越,邱志雄,金一垂.不同視點重疊圖像自動拼接算法.中國航海，2001，(2)：41-45