時間：2022-02-07 10:26:01
開篇：寫作不僅是一種記錄，更是一種創造，它讓我們能夠捕捉那些稍縱即逝的靈感，將它們永久地定格在紙上。下面是小編精心整理的12篇匹配算法論文，希望這些內容能成為您創作過程中的良師益友，陪伴您不斷探索和進步。
關鍵詞：Rete算法，智能防火墻，規則，快速，匹配
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)
[3] 江建國，張景中. 基于Rete算法的幾何自動推理系統. 四川大學學報（工程科學版）， 2006(03)
關鍵詞：KMP；改進；模式匹配算法；字符；分析；算法
中圖分類號：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.
[6]趙森嚴，黃偉，李陽銘.一種改進的KMP入侵檢測的模式匹配算法[J].井岡山大學學報（自然科學版），2013（01）：55-57.
【摘要】 頸動脈超聲圖像中的運動信息能夠間接地反應頸動脈彈性等狀況，結合頸動脈內中膜厚度(CIMT)能夠為心腦血管疾病診斷提供定性與定量的依據。我們將改進后的金字塔快速匹配算法(modified block sum pyramid，MBSP)應用于頸動脈超聲波圖像斑點跟蹤獲得運動信息。理論和實驗結果都表明，改進后的金字塔塊匹配算法能有效地減少運動跟蹤的運算量，并且有著和改進前的金字塔塊匹配算法相同的準確度。運動跟蹤結果能夠為醫生診斷心腦血管疾病起到一定的輔助作用。
【關鍵詞】 頸動脈;斑點跟蹤;金字塔算法;運動分析;平均絕對差函數
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.
[7]Demir B， Ertu¨rk S. Block motion estimation using adaptive modified two-bit transform[J]. IET Image Process， 2007，1(2):215-222.
關鍵詞：數字圖像取證；圖像區域復制粘貼篡改
中圖分類號：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
[2]駱偉祺,黃繼武,丘國平.魯棒的區域復制圖像篡改檢測技術[J].計算機學報,2007,11
關于樹葉質量的建模與分析
封鎖嫌疑犯的數學建模方法
正倒向隨機微分方程理論及應用
數學建模與數學實驗課程調查報告
基于膚色模型法的人臉定位技術研究
生豬養殖場的經營管理策略研究
從數學建模到問題驅動的應用數學
大學籃球教練能力評價的機理模型
基于WSD算法的水資源調度綜合策略
關于地球健康的雙層耦合網絡模型
多屬性決策中幾種主要方法的比較
塑化劑遷移量測定和遷移模型研究進展
基于信息熵的n人合作博弈效益分配模型
混合動力公交車能量控制策略的優化模型
垃圾減量分類中社會及個體因素的量化分析
隨機過程在農業自然災害保險方案中的應用
“公共自行車服務系統”研究與大數據處理
天然氣消費量的偏最小二乘支持向量機預測
微積分與概率統計——生命動力學的建模
美國大學生數學建模競賽數據及評閱分析
微積分與概率統計——生命動力學的建模
在微積分教學中融入數學建模的思想和方法
2015“深圳杯”數學建模夏令營題目簡述
字符串匹配算法在DNA序列比對中的應用
差分形式的Gompertz模型及相關問題研究
小樣本球面地面條件下的三維無源定位算法
數學建模思想滲入代數課程教學的試驗研究
基于貝葉斯信息更新的失事飛機發現概率模型
基于人體營養健康角度的中國果蔬發展建模
關于數學成為獨立科學形式的歷史與哲學成因探討
深入開展數學建模活動,培養學生的綜合應用素質
完善數學建模課程體系,提高學生自主創新能力
利用動態貝葉斯網構建基因調控網絡的研究進展
地方本科院校擴大數學建模競賽受益面的探索
城鎮化進程中洛陽市人口發展的數學建模探討
基于TSP規劃模型的碎紙片拼接復原問題研究
卓越現場工程師綜合素質的AHP評價體系研究
基于Logistic映射和超混沌系統的圖像加密方案
嫦娥三號軟著陸軌道設計與控制策略問題評析
嫦娥三號軟著陸軌道設計與控制策略的優化模型
微生物發酵非線性系統辨識、控制及并行優化研究
含多抽水蓄能電站的電網多目標運行優化研究
連接我們的呼吸:全球環境模型的互聯神經網絡方法
垃圾焚燒廠周邊污染物濃度的傳播模型和監測方案
以數學建模競賽為切入點,強化學生創新能力培養
一種新的基于PageRank算法的學術論文影響力評價方法
基于視頻數據的道路實際通行能力和車輛排隊過程分析
[關鍵詞]通信技術；交通流，GPS定位
中圖分類號：TN 文獻標識碼：A 文章編號：1009-914X（2014）23-0203-01
1.研究內容
手機定位技術是利用移動通信網絡和移動通信設備進行手機定位的，只要能夠實現雙向通信的移動通信系統都可以作為這種定位系統的通信基礎，如國內移動運營商較多采用的GSM系統、CDMA系統等。現階段，國內兩大主要移動運營商移動、聯通均已推出了手機定位服務。
無線定位系統中將手機定位方式分為：基于網絡方式及利用移動網絡的基站獲得手機位置信息，該方法不需要對現有的手機設備進行任何改進；基于手機終端的方式，該方法需要對現有手機設備進行一定的改進；以及兩者的混合式定位方式。可見，將基于網絡的手機定位數據作為交通檢測信息不需要過多的基礎設施投資，能夠實現低成本、實時的交通流參數檢測。
比較實用的GPS定位技術是網絡輔助的GPS定位，即定位時，網絡通過跟蹤GPS衛星信號，解調出GPS導航信號，并將這些信息傳送給移動臺，移動臺利用這些信息可以快速的搜索到有效的GPS衛星，接收到衛星信號后，計算移動臺位置的工作可以由網絡實體或移動成。基于GPS系統的定位技術，其優點是定位精度較高，定位半徑可達到幾米、十幾米。因此利用該重定位技術，可提供對定位精度要求較高的業務，如電子地圖顯示用戶位置等。其缺點是需要移動臺內置GPS天線和GPS芯片等模塊，并且需要支持IS-801協議，網絡側需要增加PDE和MPC；定位精度受終端所處環境的影響較大，如用戶在室內或在高大建筑物之間時，由于可見的GPS衛星數量較少，定位精度將降低，甚至無法完成定位。
GPS（AssistedGPS）。A-GPS與GPS方案一樣，也需要在手機內增加GPS接收機模塊，并改造手機天線，但手機本身并不對位置信息進行計算，而是將GPS的位置信息數據傳給移動通信網絡，由網絡的定位服務器進行位置計算，同時移動網絡按照GPS的參考網絡所產生的輔助數據，如差分校正數據、衛星運行狀態等傳遞給手機，并從數據庫中查出手機的近似位置和小區所在的位置信息傳給手機，這時手機可以很快捕捉到GPS信號，這樣的首次捕獲時間將大大減小，一般僅需幾秒的時間。不需像GPS的首次捕獲時間可能要2―3分鐘時間。而精度也僅為幾米，高于GPS的精度。
在移動電話定位系統中，可以利用不同的信號特征參數，如信號強度（SS）、信號到達角度（AOA），時間測量值（包括信號到達時間TOA、信號到達時間差TDOA）等，以及他們的組合進行定位。各種定位方法采用的信號特征參數、信號檢測設備、實現定位的難易程度、信號傳播中的影響因素和定位的精度都不相同，但提供“微觀”車輛運行狀態的車載手機定位數據的確具有相同的數據特征，與傳統檢測器提供的車輛通過信息的數據特征完全不同。
從數據的檢測對象上看，基于GPS定位的交通流參數估計，已采集道路車流中行駛的裝配GPS定位裝置的車輛自身的行駛數據――多點定位位置、瞬時速度數據及車輛的一些其他狀態信息為基礎，進而獲得檢測車輛所在道路的交通流參數。基于移動通信網絡的手機定位信息包括公路沿線手機的ID號和經緯度，利用上述手機信息獲得獨立車輛運行狀態，進而估計信息間的單元所在路段的交通流參數。
可見，基于傳統檢測器和GPS定位檢測器的交通流參數估計均是以車輛為檢測目標，檢測車輛的通過或存在狀況，獲得道路上的獨立車輛信息。而基于手機定位的交通流參數估計卻以道路上行駛車輛的車載手機為檢測目標，通過車載手機信息獲得獨立車輛狀態。
標定切換網絡
切換網絡由切換點和切換路段構成，其中切換點指的是車載手機在道路上發生手機切換的位置；切換路段指的是連續發生兩次手機切換的路段。在沿途道路上標定出基站切換或手機切換點的位置，利用預先準備的專業軟件經實地測試獲取切換點坐標，計算出切換網絡中每條道路的路段長度，如圖所示。其中（1，3）就是一個被標定的切換點，表示手機從基站1到基站3的切換點位置坐標；L1就是兩個手機切換點A（1，3）和B（3，6）之間的路段長度。
2.路徑匹配
與預先得到手機位置獲取交通信息方式不同，基于手機位置切換技術的路徑匹配是利用沿路行駛的車載手機切換序列來確定手機所處路段。在理想狀態下，手機在兩基站覆蓋范圍交界處發生切換，每條道路都有與之對應的一條穩定切換序列，按照上面原理示意圖，根據已標定的切換網絡，得到與實際道路對應的手機切換序列1-3-6-9-10-12-15-18-26，當通過七號信令解析出來的GSM網絡中的小區部分或全部標識與這條道路的切換序列相一致，就能對該車載手機的行駛路徑匹配到該路段中。例如，采集到手機的切換序列為1-3-6-9、9-10-12、12-15-18-26等，都可以確定車載手機在該條道路上行駛。
另一方面，由于手機信號受多方面因素影響，如城市內的高層建筑對信號的反射和折射、其他通信信號對手機信號傳播的干擾等，都對手機切換造成不穩定影響，也降低了路徑匹配概率，需要進一步研究這些現象，讓兩者關系趨于穩定。
計算路段行程車速
完成切換網絡標定和路徑匹配之后，就可以計算每條道路上的路段行程車速。手機至少連續發生兩次位置切換才能得到手機行駛的路段長度Li， 這時根據Vi=Li/ti 即可計算出車載手機的行駛速度。以此類推，就可以獲取切換序列中，手機對于所有相應路段的行駛速度。
3.地圖匹配技術的算法
地圖匹配算法的要求
地圖匹配的結果需要盡可能的減小車載手機的軌跡坐標與行駛車輛的實際位置之間存在的影響誤差，正確顯示車輛在地圖上的具置，提高系統信息采集的穩定性和可靠性。因此，地圖匹配的算法就需要滿足以下要求：
選用的算法具有實時性：算法簡單，可以隨時調整車輛行駛軌跡，減少時延估計；
選用的算法具有適應性：算法針對復雜交通路況都可以進行匹配，不受單一道路條件局限；
選用的算法具有可靠性：算法在復雜路網上，可以選擇正確的候選道路；
算法要求距離因素：車輛實際位置與地圖匹配道路之間的距離應最短；
算法要求方向因素：車輛行駛軌跡與地圖匹配道路方向保持一致；
算法要求道路連通性因素：車輛行駛上一時刻的位置的匹配于一條道路上，則當前時刻的車輛位置也匹配于該道路上，或者匹配于與該道路連通的道路上；
算法要求路徑長度因素：在某一時間間隔內，車輛行駛的實際距離與匹配到地圖上的路徑長度基本相同；
對于蜂窩無線定位，還需考慮兩個因素：
【關鍵詞】語音識別 語音輔助 辦公系統 有限狀態機
語音交互是人們最廣泛使用和適應的一種日常交互方式，在電子信息領域，也是一種理想的人機交互方式，隨著語音識別算法的發展和相關硬件技術進步，語音識別技術逐步走向成熟，目前在語音輸入領域、語音大數據分析、語音生活輔助等領域已經有較多的應用場景。但是語音輔助技術目前仍存在一定難點，例如語音開集庫識別、語音交互速度等方面。同時，語音識別技術在辦公輔助系統上應用還較少，尤其是某些工作人員不方便進行手動指令輸入操作的場景或手動指令輸入效率較低場景，如果利用語音輔助技術，可以有效提高用戶辦公效率和系統適應性。
本文基于上述問題，針對性地提出了一種語音輔助系統模型，通過合理的模型設計和算法設計，有效改進了上述技術難點帶來的語音識別效率和指令輸入效率問題，提高用戶使用語音輔助時的工作效率和用戶體驗。
1 系統概述
1.1 系統整體框架介紹
系統整體框架如圖1所示，系統分為三層架構，分別為用戶交互層、邏輯處理層和底層框架。用戶交互層主要負責與用戶進行指令交互工作和信息反饋工作，主要包含三個模塊，為語音監聽模塊、用戶輸入模塊和語音反饋模塊，三個分別負責用戶語音監聽，用戶手動指令輸入和系統信息語音反饋。
邏輯層為系統核心部分，包含模式識別模塊、指令執行模塊和語音識別模塊，其中，語音識別模塊獲取交互層提交的用戶語音音頻信息，將用戶語音指令或語音輸入轉換為輸入字符串，以便進一步處理。模式識別模塊的主要作用是將用戶輸入語音轉換獲得的字符串進行模式匹配，將無結構的字符串轉換為結構化的指令樹，從中提取用戶真正的指令信息。指令執行模塊的主要功能是進行用戶數據和系統操作的指令執行，其中為其他模塊提供系統操作接口，供其他模塊調用。
底層框架提供了系統基礎運行平臺，分別包含系統運行框架和數據庫平臺，底層框架根據不同的系統部署要求可以進行對應的調整。
2 系統關鍵部分
2.1 語音監聽與識別模塊
語音監聽與識別屬于用戶交互端和邏輯預處理端，其核心部分為語音識別技術（Auto Speech Recognize，簡稱ASR），在本論文的實現過程中，采用科大訊飛的語音識別SDK，其語音識別算法采用深度神經網絡（DNN）聲學建模，同時采用多重降噪算法進行降噪處理，經測試，能夠充分滿足本系統針對的多樣化使用場景需求。
系統在啟動后，語音監聽模塊將進行常駐監聽，保證用戶指令隨時處于輸入狀態，減少用戶手動操作效率降低問題，獲取語音信息經壓縮后傳遞給語音識別模塊，語音識別模塊將音頻信息識別后轉換為字符串，此生成信息作為模式匹配樣本交給邏輯層處理。
2.2 指令模式識別模塊
指令識別模塊的主要作用是獲取經過對用戶輸入語音轉換后的字符串，通過與系統預先設置的用戶指令進行對比匹配，提取用戶輸入信息中的指令部分，再交由指令執行模塊進行信息處理。
為提升用戶指令匹配成功率，在指令模式識別過程中，采用有限狀態機模型（Finite-state machine），采用有限狀態機，可以建立指令樣本，在對用戶輸入信息進行指令匹配時，采用順序字符串匹配算法，這樣可以高效過濾用戶信息，快速提取用戶指令。
3 系統關鍵技術
3.1 基于有限狀態機的指令匹配模型
此部分主要包含兩個方面，一是系統指令的預設定，如上文所述，在某信息系統嵌入該語音輔助系統時，首先要確定該系統所需要對用戶提供的指令內容，將每個指令內容作為有限狀態機中的單一狀態，例如圖2所示。
第二部分為用戶輸入信息指令提取，由于用戶指令數有限，所以，在獲取用戶模式匹配樣本之后，可以采用順序字符串匹配計算，當匹配到預設指令時，便將該指令作為狀態機狀態轉移標志，進而獲取用戶所需要進行的操作，達到指令匹配目的。在匹配過程中，采用KMP算法，有效提高用戶指令輸入效率。
3.2 指令快速匹配優化
在大多數信息系統中，除了用戶操作有限之外，還具有上下層級關系，為提高用戶輸入效率，在系統初始化設定過程中，針對具有層級關系的指令，將其構筑為指令樹結構，如圖3中所示，如果用戶輸入指令為“AABB0246CC”，系統在匹配至“0”時，將不再向用戶返回確認請求，將繼續進行指令匹配，直至匹配至“C”，那么最終狀態將跳轉至狀態7，向用戶返回請求指令7執行，得到確認后，將執行指令。按照上述流程，在面對多層指令操作時，用戶只需要語音輸入連續狀態指令，將直接跳轉至目標狀態，執行目標執行，達到指令快速匹配目的，這樣極大提升了用戶輸入效率，省去大量重復語音指令輸入步驟。
4 總結
目前語音識別正在進入越來越多的領域，利用本文設計的語音輔助系統，用戶指令輸入效率得到顯著提升，同時給出整體模型，以便其他信息系統平臺高效接入此語音輔助系統。
參考文獻
[1]王炳錫.實用語音識別基礎[M].北京：國防工業出版社，2005.
[2]童拉.辦公自動化系統中語音功能的設計和實現[J].湖北工業大學學報，2005，20（02）：71-73.
[3]訊飛開放平臺.科大訊飛股份有限公司.2017.http：///.
查看更多《信息技術》雜志社信息請點擊： 《信息技術》編輯部
基金項目
(1)基于c＋＋ builder的共焦顯微鏡三維重建方法 楊召雷 張運波 董洪波
(4)m—link在通信系統仿真中的設計與實現 姚云龍 周俊 劉強
(8)基于嵌入式的無線煤炭自燃預警系統 劉德文 杜宇人
(11)tts語音單元的無損壓縮與按需解壓縮技術 卡斯木江·卡迪爾 古麗娜爾·艾力 艾斯卡爾·艾木都拉
無
(14)2012年中國國際信息通信展覽會開幕 無
基金項目
(15)低載荷工業機器人運動學分析與仿真 陳蓓玉 胡凱 楊樂
(19)基于zigbee無線傳感網絡監測系統的實現 楊俊 阮超 陳睿瑤 付紅橋
(23)endnote x5軟件在論文撰寫過程中的應用 程宏輝 程筱農 奚和平 黃新
(26)一種近距離無線傳感器系統的設計 葉天鳳 胡長暉 葉夢君 萬里光
(29)sakai網絡教學平臺統一身份認證中心的實現 柯水洲 馬雪梅 王新舸 鄒剛
(33)增益連續可調寬帶前置放大電路設計與實現 汪俊杰 蓋建新 劉旭 程爽
(37)actionscript3.0垃圾回收機制及優化策略 李智勇
(40)基于彩信的遠程控制寵物籠系統的研制 楊樂 高超
(42)spring mvc技術分析及在實踐教學系統中的應用 符紅霞
(47)支持向量機在廣義預測控制中的應用 張偉 賈蓉
(50)測控信息技術領域提高學生實踐創新能力的方法 王可寧 劉纏牢 王偉 張雄星
(53)一種復雜背景下車牌定位算法 趙大偉 陳剛
研究與探討
(58)基于spce061a的語音手動雙控制開關的設計 李建新 張肖飛 徐麗妍
(62)基于bp神經網絡的鉆井復雜情況和事故診斷 崔猛 汪海閣 李洪 紀國棟 于洋
無
(65)第九屆通信企業管理現代化創新成果審定會開幕 無
研究與探討
(66)一種基于單攝像頭的虛擬鍵盤 楊騁
(68)基于橢圓曲線的充值卡加密 孫傳亮 周海港
(72)基于ccd和光電編碼器的差速整定方法研究 李增彥 張迪洲 張男
(77)嵌入式軟件仿真測試平臺開發 林丹丹
(80)基于anybus-s pn io模塊的profinet遠程i/o設計 楊明 王永剛 張陸毅
(85)采用mel倒譜參數的咳嗽聲識別方法 尹永 莫鴻強
(92)模板匹配算法的兩種實現方法比較 謝方方 楊文飛 陳靜 李芳 于越
(96)基于msp430的低頻信號分析儀設計 張君 李金龍 郭建強 楊林曉
(101)基于labview的雙向智能鑰匙充放電測試系統 尹武 張文娟 周繼宇
br> (104)多用途市電負載功率調功電路的設計 姚正武 部紹海 林濤 李樹偉
(107)gps周跳探測與修復方法的比較分析 徐歡 唐亮 都業濤
(112)并行計算技術綜述 王磊
(116)衛星遠程監視及實時故障診斷研究與應用 陳懷木 賈銀山 穆友勝
(121)基于soa的一體化繳費接入管理平臺設計 王樹全 鄒寧峰 金鑫
(125)基于增量式pid控制算法的智能車設計 肖文健 李永科
應用技術
(128)油層保護模糊專家系統的分析與設計 張丹 曹謝東 魏存擋 龐揚
(131)基于multisim10低頻信號源的設計與仿真 蘭羽 周茜
(134)光電池基本特性的測定 趙楠 孫雪萍 李平舟
(137)基于單片機的無視頻報警監測儀設計 李釗
(140)基于hfss的有孔屏蔽體的屏蔽效能分析 陳新平 楊顯清
(144)戰術無線電臺半實物仿真系統設計與實現 張愛民 辛廣輝 鄭振華
(147)基于混合高斯模型與核密度估計的目標檢測 呂游 任政 李向陽 方向忠
(151)基于業務流程的信息化建設與應用 劉光偉
(153)基于國產cpu的嵌入式醫療電子無線網絡設計 裴家俊 張輝 劉蕓 戎蒙恬
(157)利用vba及office自動化技術輔助人事辦公 王晶
(159)數字鐘電路的設計 曹嘯敏
(163)基于電磁傳感器的智能車自主尋跡系統設計 師克 王洪軍 李永科
無
(166)上海市中國軟件名城創建暨軟件產業工作會召開 無
應用技術
(167)異步時鐘亞穩態仿真方法 高文輝 胥志毅 鄔天愷 劉文江 仲景尼
(170)lwip的移植及其在并行系統中的應用 趙虎 黎英 游謙
(173)盲人行走輔助裝置中道路檢測算法的研究 徐姍姍 應捷 宋彥斌
無
(176)尚冰出席第八屆中國信息無障礙論壇開幕式并致辭 無
應用技術
(177)多載波傳輸系統的頻偏及采樣鐘聯合補償算法 李炎 周志平 李鑫
(181)智能小車模糊-pid控制調速系統設計 張家驊 徐連強 吳迎春
無
(183)第九屆海峽兩岸信息產業和技術標準論壇舉行 無
綜述與評論
(184)epc信息管理系統在裝備器材保障中的研究 康帥 高慶 程遠增
(187)基于供應鏈信息共享的備件資源整合研究 黃健 程中華 王亞彬
(190)航空航天偵察情報保障能力綜合評價模型研究 童濤 楊桄 譚海峰 王壽彪 葉怡
(194)裝備保障信息評價研究 趙國存 劉占嶺
無
(f0003)
關鍵詞：XML數據；節點加權；樹編輯距離；相似性
中圖分類號：TP391.1
隨著網絡快速發展，由于結構化的XML類型數據可擴展且跨平臺而成為當前網絡數據的主流形式。XML文檔的迅速增多并集成統一平臺后，會產生不被需要的“臟數據”，而對這些數據的清洗變的更加重要。這些“臟數據”使輕則會使獲得的信息不準確，重則獲得完全錯誤的信息。為了使XML數據源中的數據能發揮最正確的作用，清洗平臺中的“臟數據”成為一個組要解決的問題。
非一致性轉換、相似性判定、信息抽取等3方面是當前XML數據清理的主要關注點。如韓愷等人提出的在上下文語義影響下的XML文檔的匹配方法[1]，Flesca等人將結構化的XML文檔與時間序列、脈沖等內容聯系起來進行相似性檢測[2]。以上兩篇文章關于XML數據清理方法考慮了不同DTD樹間的匹配算法，其中文檔內容提到較少，部分方法設計思想很好，但實踐可行性有限。
首先，將一個XML文檔轉化為一棵樹或一個圖，然后通過度量這兩棵樹（圖）間的距離來體現XML文檔間的相似度。在眾多樹相似度匹配的研究工作中，普遍接收和采用的既是樹編輯距離算法[3-6]。Tai[3]最早將編輯距離的方法應用到檢測兩顆樹間的相似性。以他的理論為基礎，提出的一系列樹編輯距離算法及相關的改進算法等。
1 相似重復記錄
信息集成中，數據清洗和提高數據質量是檢測和消除集成數據中的相似重復記錄中最需要解決的問題之一。相似重復記錄的概念是指雖然在現實世界中表述的是同一個實體，但由于拼寫錯誤或表達方式的不同，而導致數據庫管理系統不能將其識別為重復的記錄。這些重復記錄的產生導致決策者在最終決策時由于依據的信息不正確而產生較大的影響。以此為基礎，重復記錄檢測在信息的抽取、轉換、加載的過程中顯得更加重要。目前研究的主要方向體現在西文、中文字符集的相似重復記錄的檢測，已有了一定研究。但對于半結構化的XML數據的重復記錄檢測算法的研究還有待進一步提高。
XML數據在網絡中使用的增多以及在數據庫中的使用，使得這種數據類型在數據清理中越來越重要。實際多種XML數據被認為不一致，例如拼寫錯誤等導致字符串屬性不一致，從而使得此字符串類型數據不一致。另外，實際相同的XML數據由于結構上不同被認為是不同的數據。即使數據源具有相同的DTD結構，屬性個數不同、屬性值拼寫不同均可導致XML數據不一致。
在XML數據的ETL中，主要摒棄其中的“臟數據”，也就是檢測出相似記錄合并，普遍采用的方式即將XML文檔轉換成樹結構，轉換的過程中要將樹中的節點與數據元素相對應，即節點名為元素標簽名。編輯距離方法分為兩種，字符串編輯距離算法用判定兩個字符串是否相似，而通過樹編輯距離方法時大家更清晰的認識到帶標號有序樹間差異。以下給出與樹編輯距離相關的概念定義。
2.1 基本概念
目前對于數據相似性的檢測主要采用編輯距離的方式，而此方式又分為兩種，字符串編輯距離主要用于字符串領域，樹編輯距離主要應用于兩棵樹或圖的差異檢測，以下給出具體概念描述。
（1）字符串編輯距離：定義字符串S1、S2，當S1轉換為S2時所需要的編輯操作的最小數目，此轉換指單個字符上的轉換，而操作主要指插入、修改、刪除。此概念普遍應用于字符串的相似性檢測。
（2）樹編輯距離：定義兩棵樹T1、T2，當T1轉換到T2時所需要的書編輯操作的最小代價，此轉換指節點的轉換。而節點的插入、刪除、修改三種操作稱為樹編輯操作：
1）修改（替換）：節點改變；
2）刪除：刪除某一節點的同時，將該節點的兒子節點重新定義為兄弟節點并插入到其父節點的子樹中；
3）插入：插入某一節點的子節點，而該節點的原部分子節點轉換為新插入節點的子節點。
樹編輯距離體現了在兩個樹轉化的過程中樹編輯操作的最小次數，而實際編輯操作次數計算方式可以通過映射這一概念來體現，將整個求解過程解釋為樹之間的映射過程，稱為編輯映射。
（1）樹編輯距離算法：定義兩個樹T1和T2，在兩個樹之間建立一映射，直接體現了樹與樹節點間的對應關系。在樹與樹之間建立映射需要滿足一系列的條件，首先給出兩組對應關系屬于此映射，分別為（i1，j1），（i2，j2），其中1≤i、j的值≤樹的節點數，則，當且僅當j1≤j2時，i1≤i2；另外當且僅當節點j1是節點j2的祖先是，節點i1是節點i2的祖先，從而將樹編輯距離的計算轉換為映射的計算，在計算過程中，最好的結果即是所付的代價最小。
（2）樹編輯距離相似性檢測：XML類型數據相似性的檢測可以分兩步走，首先計算文檔轉換為樹結構時，數據所對應的節點元素字符串間的差異，然后把字符串差異的計算合并到樹編輯距離的計算之中來。樹編輯距離的值越小，則兩顆XML樹越相似，此過程中給出閾值的概念作為評判的標準，當值小于設定的閾值時，認為兩個XML數據相同。
3 優化的XML相似重復數據檢測算法
時間復雜度體現了完成操作所需要付出的代價，而針對上述的樹編輯距離算法其時間復雜度跟樹的節點數以及樹的高度有直接的關系。因此，當XML文檔的數據量足夠大的時候，計算代價會成倍增長，這在實踐過程中是無法忍受的，因此，必須采用優化措施來減少樹編輯距離計算。本文優化樹編輯距離算法，在整個過程中，首先通過樹節點的權值進行第一次匹配，將相似性更大的數據聚集到一個集合中，在此集合中采用樹編輯距離方法進一步匹配，從而減少時間復雜度。
3.1 帶權樹的生成
由于XML文檔可以轉化為多種樹表示形式，針對XML文檔通過SAX（Simple API for XML）解析器進行解析，將XML文檔轉化為XML樹結構，并具有相應的可行匹配方法。根據解決問題的側重點不同，XML帶權樹的屬性在XML文檔中具有不同的重要程度。通過XML帶權樹的權值的大小來表示屬性的重要性。根據權值本身的設置特點，在帶權樹中，設置相同根節點的同一層次上的節點權值之和等于1。
3.2 相似性粗略匹配
針對完全展示XML文檔的信息的帶權樹，通過權值的不同體現每個元素重要程度的不同。通過權值進行粗略匹配主要體現在XML樹的屬性相同時，權值是否相同，權值差異越小，則判斷樹的相似性越高。在整個判斷的過程中，還需要考慮到屬性的多少，即樹分支數目。
通過實際情況分析推測出重復記錄相似度的計算方法如下：帶權樹Ta和Tb，N代表兩樹所有節點的個數，a1 a2 … aN，b1 b2 …bN分別代表權值，其體現了屬性的重要程度。另外，當某一屬性僅存在于一棵樹中時，則設定此屬性的權值為0，相似度的計算公式見（1）[7]：
S（Ta，Tb）=（N-（a1-b1+a2-b2+ … +aN-bN））/N
=1-（ （ai-bi））/N （1）
上述公式作為相似度計算的工具，可以很好的計算出任意XML帶權樹之間的相似性，通過具體的數據來體現差異的大小，從而進行簡單的匹配，節省時間。
根據以上描述給出XML類型數據相似性檢測的偽代碼算法描述如下：
（1）將輸入的XML數據集轉換為XML帶權樹；
（2）通過節點權值來計算兩棵帶權樹間的相似度，從而粗略匹配數據；
根據上述思想給出粗略匹配的偽代碼描述。
（a）從所有的XML樹中任取其中一棵樹；
（b）以所取樹為基準，通過相似性度量公式計算基樹與其它樹之間的相似度，目的為了得到所有的相似度值；
（c）將上述相似度值與系統輸入的相似度量λ進行比較，若大于等于λ；
（d）將相似度值大于等于λ的XML樹聚合成新的集合C1；
（e）任取一不在集合C1中的帶權樹Tb；
（f）重復執行步驟（b）；
（g）直到所有的帶權樹均存在于一個集合中。
（3）在經過第（2）步聚集的所有新集合中使用樹編輯距離算法，當計算后的距離值小于給定的閾值δ時，認為兩個是相似的XML數據。
4 結束語
本文首先介紹了一系列概念定義，包括相似重復記錄，兩種編輯距離，并詳細描述了樹編輯距離相似性檢測算法及相關問題。在此基礎上，提出一種檢測XML數據相似性的方法，即將XML文檔轉換成樹結構的基礎上，對樹結構的節點加權，并結合樹編輯距離算法。通過XML帶權樹各屬性權值計算的相似度對數據進行粗略匹配與聚集，而在重新聚集的集合中使用樹編輯距離算法更直接的進行相似性檢測。該方法可以大大減少不必要的樹編輯距離操作。
參考文獻：
[1]韓愷，岳麗華等.基于上下文的異構文檔類型定義匹配[J].小型微型計算機系統，2005，26（02）：256-260.
[2]Flesca S，Manco G，Masciari E et al. Detecting structural similarities between XML documents.In：Fernandez MF，Papakonstantinou Y，eds.Proc.of the Int’l Workshop on the Web and Databases（Web DB）.2002：55-60.
[3]Tai K C.The tree-to-tree correction problem. Journal of the ACM， 1979，26（03）：422-433.
[4]David T. Barnard，Gwen Clarke et al.Tree-to-tree Correction for Document Trees，1995.
[5]Zhang K，Shasha D.SIMPLE FAST ALGORITHMS FOR THE EDITING DISTANCE BETWEEN TREES AND RELATED PROBLEMS，1989，18（06）：1245-1262.
[6]Zhang K.Algorithms for the constrained editing distance between ordered labeled trees and related problems，1995，28（03）：463-474.
[7]江曼，陳繼明，潘金貴.基于XML的層次式過濾研究[A].2006年全國體育儀器器材與體育系統仿真學術報告會論文集[C].2006.
關鍵詞：偽二維隱馬爾科夫模型；符號識別；圖像匹配
中圖分類號：TP312
目標的檢測與識別主要應用于智能交通領域，如飛機、艦船、車輛等目標的檢測與識別跟蹤[1]。要實現圖像目標的檢測與識別，一方面可以通過一些圖像處理的手段消除影響因素使其得到比較規范的數據；另一方面就可以尋找目標圖像上能夠保持恒定不變的某些特征參數來建立該類目標的表述模型。建立了這樣的目標影像的表述模型后就能實現影像目標有效識別。第一種方法雖然是一個行之有效的方法，但是它需要一系列繁瑣的預處理，效率很低；本研究主要是考慮提取標更一般化的不變量特征。
基于偽二維隱馬爾科夫模型（Pseudo Two-Dimensional Hidden Markov Model-P2DHMM）的識別方法[2]，是基于P2DHMM模型的拓撲結構進行圖像的匹配，計算得出P2DHMM距離，利用最近鄰原則判別，沒有固定的模板參量限制，因此P2DHMM在手跡識別、人臉識別和醫學圖像方面得到成功的應用[3-4]。本研究將P2DHMM引入到圖像符號的識別中，工作重點放在三個方面：（1）研究圖像中基于P2DHMM目標識別的二維非線性變形模型的適用性和潛在應用價值；（2）實驗模型的拓撲結構、主要參數和算法選擇；（3）建立典型參考圖像符號庫，進行了圖像符號識別實驗并分析結果，提出模型改進的建議。
1 偽二維隱馬爾科夫結構與特征參量構建
1.1 隱馬爾科夫模型與偽二維隱馬爾科夫模型
隱馬爾科夫模型（HMM）是在馬爾科夫鏈的基礎上發展起來的，由于實際問題比馬爾科夫模型所描述的更為復雜，觀察到的事件并不是與狀態一一對應，而是通過一組概率分布相聯系，這樣的模型就稱為HMM。它是一個雙重隨機過程，其中之一是馬爾科夫鏈，這是基本隨機過程，它描述狀態的轉移；另一個隨機過程描述狀態和觀察值之間的統計對應關系[5]。
二維隱馬爾科夫模型（2DHMM）是由HMM模型演變而來，它由水平方向HMM和垂直方向HMM構成，水平HMM中的某一狀態不僅可以轉移到水平方向的其它狀態，同時還可以躍遷到垂直方向HMM中的某一狀態，同樣的垂直方向HMM中的狀態也可轉移到水平方向。由于二維HMM的結構的復雜性，算法復雜，限制了2DHMM的應用[6]。
偽二維隱馬爾科夫模型（P2DHMM）利用了一維HMM的基本拓撲結構，將一個完整的一維HMM作為一個狀態，形成P2DHMM的超狀態，超狀態里面的一維HMM的狀態是子狀態。子狀態只能在相應的狀態約束下進行躍遷，超狀態與子狀態之間也不允許躍遷，但是在超狀態之間有狀態轉移。由于這一模型中不同超狀態下的子狀態之間不能夠躍遷，因而不是真正意義的二維模型，故也被稱為偽二維隱馬爾科夫模型，見圖1。每個超狀態為一個隱Markov模型單向左右型的拓撲結構，超狀態間轉移的拓撲結構也為單向左右型。P2DHMM模型已被成功地應用于字符識別、人臉識別等領域。
圖1 P2DHMM的拓撲結構圖
1.2 基于P2DHMM拓撲結構的圖像匹配
基于P2DHMM拓撲結構的圖像匹配，沒有進行目標的特征的提取直接用圖像的灰度值進行匹配。
具體匹配算法如下所述：
假設，測試目標圖像用A=（aij）表示，其中每個像素的位置為（i，j），i=1，……，I，j=1，……J。
參考目標圖像用B=（bxy）表示，其中每個像素的位置為：
X=1，……，X，y=1，……，Y。
基于P2DHMM拓撲結構的測試圖像和目標圖像之間進行匹配滿足的約束為：
x（1，j）=y（i，l）=1
x（N，j）=y（i，N）=N
0≤（xij-xi-1j）≤2
|xij-xij-1|=0
0≤（yij-yij-1）≤2 （1）
此約束忽略了相鄰的列的像素之間的依賴關系，相鄰列之間的垂直方向的相對置移被忽略，圖像間的映射為列到列的映射，映射關系滿足P2DHMM超狀態的轉移。每列內的像素之間的映射也是滿足超狀態內的子狀態之間的轉移。
超狀態之間的轉移是從左到右，子狀態之間的轉移是從下到上，躍遷都不超過2個像素寬。像素和其相鄰的像素之間的關系保持下來，參考圖像的二維變形圖像保持了原始圖像的結構特征。
通過基于P2DHMM的拓撲結構對兩圖像進行匹配，我們得到樣本B的變形的圖像B（xIJ11，yIJ11）。A，B圖像之間的距離，就轉化成A和B（xIJ11，yIJ11）之間的距離。
（2）
1.3 圖像水平方向約束的補償與構建特征參量
P2DHMM不是真正的二維，放松了水平方向的約束，目前通常采用兩種方法對這種假設進行補償[6-7]。第一種方法是對圖像進行Sobel濾波（包括水平和垂直方向），得到圖像的梯度圖，在梯度圖的基礎上進行識別。第二種方法是加入像素的上下文信息，比如采用3×3的區域的上下文信息。
若用U表示3×3的區域，A和 之間的距離用歐幾里的距離公式：
（3）
現在將這兩種方法結合，對梯度圖像進行上下文信息的提取和重構。
特征參量提取的步驟：
對圖像分別進行垂直、水平方向的Sobel濾波，得到圖像的兩個梯度圖。
將兩個梯度圖上同坐標的像素3×3的區域的9個像素的灰度值取出，得到每個像素的18維的矢量表示。
得到像素垂直方向提取結果3×3（V），水平方向提取結果3×3（H），將水平方向提取結果與垂直方向提取結果排列構成18維的矢量表示。
2 技術路線與典型實驗
2.1 技術路線
從一系列圖像中，選擇200種典型的圖像符號作為試驗的參考樣本。對樣本進行縮放、旋形成測試樣本。然后進行P2DHMM匹配處理，處理技術路線見圖2：
圖2 P2DHMM匹配處理的流程圖
2.2 典型圖像符號P2DHMM匹配實驗
圖3和圖4是同種圖像符號的識別效果圖。從左到右分別是測試圖像-1，變形圖像-2，變形網格-3，參考圖像-4。上層是垂直方向Sobel濾波的效果圖，下層是水平方向Sobel濾波的效果圖，每一次匹配結果可以得到一個P2DHMM距離值。其中，變形網格是參考圖像二維變形過程中，像素的坐標位置的置移，變形圖像-2是參考圖像-4根據測試圖像得到的二維變形圖像。
如果背景相同、目標相同，測試圖像-1和參考圖像-4相同，變形圖像-2就沒有變化，變形網格-3是直角網格，P2DHMM距離值為零。見圖5。
如果測試圖像和參考圖像是同種圖像符號，發生了一定的縮放，計算得到兩圖像的P2DHMM距離值不為0，變形網格-3發生變化，P2DHMM距離值較小為6.79455。
如果測試圖像和參考圖像是不同種類型的圖像符號，計算得到兩圖像的P2DHMM距離值不為0，變形網格-3發生變化，P2DHMM距離值較大為31.76735。
圖3 同一圖像符號的匹配效果圖
圖4 縮小圖像符號的匹配效果圖
圖5 不同圖像符號的匹配效果圖
我們利用圖2的技術路線開發了圖像符號識別原型系統，取得了好的識別效果。為兩種圖像符號的識別效果圖。
圖像符號識別效果圖中。左上角為待識別圖像符號，識別結果中列出了識別出的圖像符號。識別出的圖像符號按照P2DHMM距離值的大小從左到右排序，越靠左P2DHMM距離值越小，表示與待識別圖像符號越相似。
圖6 圖像符號識別效果圖
3 結束語
論文介紹了將人工智能領域的P2DHMM模型介紹引入到圖像目標識別的模型構建、算法選擇和典型實驗的技術過程。利用基于P2DHMM的拓撲結構的約束進行測試圖像和參考圖像的匹配，保持了參考圖像的結構特征，得到更一般化的度量距離，采用了提取圖像的水平和垂直兩方向的兩幅梯度圖中像素周圍3×3 區域的像素信息表示像素值，得到像素的18維矢量表示，提高了的符號的識別率。
實驗結果展示了P2DHMM模型在圖像符號識別方面的應用潛在價值。另外，當目標背景發生變化的情況下，可以先做中值濾波處理，可以提高P2DHMM處理效果。
參考文獻：
[1]馬建文，田國良，王長耀.遙感變化檢測技術綜述[J].地球科學進展，2004（19）：192-195.
[2]史忠植.高級人工智能[M].北京：科學出版社，1998.
[3]薛斌黨，歐宗瑛.加權合成的嵌入式隱Markov模型人臉識別[J].大連理工大學學報，2002（05）：32-33.
[4]張引，潘云鶴.工程圖紙自動輸入字符識別的二維隱形馬爾可夫模型方法[J].計算機輔助設計與圖形學學報，1999（09）.
[5]D.Keysers，C.Gollan，and H.Ney.Local Context in Non-linear Deformation Models for Handwritten Character Recognition[J].In ICPR 2004.International Conference on Pattern Recognition，2004.
[6]D.Keysers，C.Gollan，and H.Ney.Classification of Medical Images using Non-linear Distortion Models[J].In BVM 2004.Bildverarbeitung für die Medizin 2004，2004（03）：366-370.
關鍵詞：危險品；混沌理論；風險分析；路線選擇
中圖分類號：F253.9 文獻標識碼：A 文章編號：1008-4428（2016）10-23 -03
一、引言
隨著社會經濟的發展，危險品運輸已經成為社會經濟活動中的一個重要組成部分。危險品運輸過程不僅是企業自身的生產運作問題，而且影響到環境、工程、經濟、社會以及政治等諸多方面，因此危險品選線問題（即確定危險品的運輸路線）通常是一個雙目標決策問題：政府管理部門追求的是盡可能減少公共風險，而運輸供應商則關心如何降低運輸成本。因此，危險品運輸選線問題成為企業、政府及國內外學者高度關注的問題之一。
國內已有關于危險品選線問題的研究，可分為定性研究和定量研究兩類：定性研究多集中在建立優化指標體系并進行綜合評價方面，而定量研究多集中于特定幾條線路的風險評價。任常興、吳宗之（2008）基于危險品道路運輸風險分析辨識最優的運輸路徑，以道路運輸事故率、影響人數、影響人員風險、環境風險、運輸距離和運輸時間6個指標，確定具體起點-終點之間危險品運輸的有效路徑，采用帶目標權重系數的Pareto-最優路線算法尋找多個滿足要求的有效解；馬昌喜（2009）研究了不發達網絡環境下危險品公路運輸路徑決策問題，在構建危險品公路運輸路徑決策指標系統的基礎上，建立了危險品路徑決策的BP神經網絡模型；楊信豐，李引珍等（2012）為了增加城市危險品運輸路徑的實用性，對側重于多屬性時間依賴網絡的城市危險品運輸路徑優化問題進行了研究。項曙光、焦巍（2013）等提出了基于模糊HSE評價的多目標反應路徑綜合方法，全面考慮HSE因素，形成了HSE指標結構，通過設定指標的隸屬度函數，建立模糊推理系統，應用層次分析法確定指標的權重因子，形成模糊評價方法。馮艷紅、劉建芹、賀毅朝（2013）針對螢火蟲算法在全局尋優搜索中收斂速度慢、求解精度低、易陷入局部極值區域等缺陷，提出一種基于混沌理論的動態種群螢火蟲算法。
國外相關研究多集中于危險品道路運輸路徑優化模型的建立及其算法研究。Erkut、Verter等（1998）從上世紀就開始從事危險品道路運輸風險定量分析的研究，認為人口暴露聚集區是平面兩維結構而不是平面中一點；Serafini（2006）建立了危險品路徑選擇問題的雙目標模型，并擴展了適用于較大網絡的動態規劃模型。Martin（2009）認為危險品路徑的選擇很大程度上是根據各路段的風險來進行的，只根據路段上的事故發生率來評價路線風險過于片面，因此在研究中引入了危險品事故率、路段事故率和工作事故率三個指標來評價風險；Bhukya、Somayajulu（2011）將混沌理論運用于DNA搜索多模式匹配算法，在初始條件產生及其細微的變化后，隨著時間的推移，最后的結果產生了巨大的差異，對多模式匹配算法的研究具有重要的借鑒意義。Abbas Mahmoudabadi等（2014）主要是運用模糊理論，基于不同風險屬性的優先級確定目標函數，建立危險品路徑選擇模型。
綜上所述，已有研究大多基于靜態風險因素結合相關優化理論與算法進行研究，而對于動態條件下運輸路徑選擇研究較少。本文針對危險品選線問題，將混沌理論運用到其中，主要闡述三個主要部分：第一部分是基于混沌理論的道路交通事故動態行為研究，時間限定在一個年度范圍內，根據危險品在運輸過程中的混沌特性，將危險品運輸過程中存在的風險分為事故、人口、環境和應急設施四個因素。第二部分根據專家意見法（德爾菲法），收集行業內專家對上述的風險因素的意見，并運用三角模糊數法將它們轉換為確切的數值。第三部分是建立基于混沌理論的危險品選線模型，并結合案例驗證結果的正確性。本文創新之處是將混沌理論應用于危險品運輸路徑選擇問題，同時結合了風險分析對各路段存在的風險因素進行研究，建立成本和風險的多目標模型，最后用一個算例驗證結果的正確性。
二、混沌理論與交通流
美國氣象學家Edvard Lorenz在1963年提出了混沌理論的概念，一些在非線性系統中突然、戲劇性的變化可能會引起復雜的后果叫做混沌理論。如果一個非線性系統對初始條件表現出敏感的依賴，那么它就被認為是混沌的，即初始條件出現很微小的差異，最終輸出結果則可能產生非常巨大的變化。混沌理論通常適用于短期預測，已被廣泛地應用于多個科學領域，特別是在交通流理論方面。混沌理論是一種兼具質性思考與量化分析的方法，用以探討動態系統中無法用單一的數據關系，而必須用整體、連續的數據關系才能加以解釋及預測的行為。
交通流中存在混沌現象這一事實已經被眾多學者的研究從多角度所證實。李洪萍、裴玉龍（2006）通過分析現有交通流預測方法，在此基礎上提出了一種基于混沌理論的交通流短時預測方法，利用基于小數據量的Wolf改進算法計算了流率序列的最大Lyapunov指數。將基于Lyapunov指數的一維預測模式具體化，建立了交通流短時預測模型，并對模型進行了改進，改進后的預測結果具有較高的精度。
Lyapunov指數是衡量系統動力學特性的一個重要定量指標，它表征了系統在向空間中相鄰軌道間收斂或發散的平均指數率。指數為正意味著在系統相空間中，無論初始兩條軌線的間距多么小，其差別都會隨著時間的演化而成指數率的增加以致達到無法預測。指數越大，說明混沌特性越明顯，混沌程度越高。公式（1）是用來確定Lyapunov指數的最大值λmax，
由于對交通行為的良好適應性，Logistic映射被廣泛應用于設定選線問題的風險因素，公式（2）為一般的Logistic映射公式，
三、 基于混沌理論的多目標模型
根據已有的研究文獻可知，道路交通事故中存在顯著的混沌行為，將風險因素通過模糊語言變量轉換成確切值，結合道路網各條邊（分段路線）的事故率，把運輸風險和運輸時間的優先順序組合作為目標函數的衡量標準，在迭代過程中更新風險因素，同時考慮不同風險和運輸時間的優先級。迭代次數取決于該時間段內代表當地專家意見的問卷調查結果。如果模糊語言變量是基于一年的基礎上，那么迭代次數應設置為365。如果是基于半年的基礎上，迭代次數應設置為180，讓所有的路徑運行此過程并比較，列出出現最頻繁的路徑組合，即為在考慮風險和運輸時間條件下危險品運輸的最佳路徑。
假設所研究的道路網為由節點i，j的各條連線（i，j）所組成的圖形G，Ns為運輸起點的集合，Nd為運輸終點的集合，第一層次的目標函數風險最小化如公式（3）所示：
式中Rsd表示從出發地s到目的地d的危險品運輸量，Wsd表示最頻繁路徑所有邊的初始運輸風險和運輸時間優先級的總和，其中s、d分別屬于集合Ns、Nd。
式中Qs表示出發地s所供應危險品運輸量的最大值，Qd表示目的地d所需求危險品運輸量的最小值。第二層次的目標函數如公式（6）所示：
式中Ksd（t）表示經過t次迭代后，所有邊的運輸風險和運輸時間加權后的總和，Pij（t）表示邊（i，j）的初始風險，Pr表示其優先級，同理TTij表示邊（i，j）的初始運輸時間，Pi表示其優先級，Pr+Pi=1意味著運輸風險和運輸時間的優先級呈負相關。
經過t次迭代后，若邊（i，j）在目標函數被選中，則Xij（t）=1，否則為0。
式中SG（t）表示根據全道路網的事故得到的事故率，MQij（t）表示利用算法把模糊語言變量轉換而得到邊（i，j）的確切風險值。
公式（9）、（10）是一維Logistic映射公式，參數K1、K2根據均方誤差最小化準則估算得到。
四、案例分析
以M省交通路網為例，每一個路段的風險因素評測主要從四個方面：事故、人口、環境和應急設施。事故因素由當地專家對該路段上碰撞事故率的意見得到，人口風險對應發生危險品運輸事故可能影響范圍的人口密度，環境風險是與影響周圍環境有關的風險，比如危險品泄漏后附近的河流、空氣等受污染程度，應急設施風險則是關于路線上應急設施的建設情況，如橋梁或隧道可能會對危險品事故發生后的救援產生影響。由當地專家給出包含上述成分的語言變量，分為五個不同程度的級別：安全、中等安全、一般、中等風險和高風險，并根據模糊層次分析法（FAHP）得出具體的風險值。
對于路網中的每一個邊，都包括事故、人口、環境和應急設施四個風險因素，確定決策者將要使用的五個語言變量，根據三角模糊數（TFN）分配給每個變量的值如表1所示。
根據模糊層次分析法的理念，將風險因素作為運輸過程中的決策指標，即事故（C1）、人口（C2）、環境（C3）、應急設施（C4），五位專家作為決策者（P1，P2， …，P5）填寫調查問卷，每個語言變量的標準權重和由專家意見法得到每個標準的權重分別如表2、表3所示。
以M省道路網中一條邊為例，五位專家根據風險的四種因素語言變量提出自己的意見并打分，利用程度分析方法將每個風險的組成部分的三角模糊數計算加總，顯示在末行。利用重要標準的權重計算風險數值，得到最大和最小風險值分別為0.8376和0.3965，歸化到此邊的風險平均值為0.7680。
結果表明，在混沌模式風險條件下選擇長路徑和短路徑而得到最終結果之間具有明顯的差異。本文所提出的方法在較長路徑中比較短路徑中效果更加顯著，主要原因是較長線路的可選路段相對多，運輸過程中不確定性更大。
五、總結
在本文的研究工作中，同時考慮到了運輸風險和運輸時間因素，其中風險由事故、人口、環境和應急設施四部分組成。由于缺乏道路交通事故的數據，運用程度分析方法將語言變量轉換成對應道路網的邊的確切風險值。對一個包括50個節點及若干個邊的省級道路網絡進行分析研究，同時對實驗數據中存在的混沌現象進行了檢驗，驗證了交通事故的混沌特征。然后運用危險品動態變量和混沌理論的基本原理相結合，建立不同風險和時間優先級的數學模型。根據一維Logistic映射方程，每迭代一次就更新動態風險的優先級。
建議以后研究危險品選線及優化問題時，可以加上諸如天氣條件和交通狀況等更多因素進一步深入研究，為決策者提供更加完備、合理的決策建議。
參考文獻：
[1]馬昌喜.危險品公路運輸路徑決策方法研究[D].蘭州交通大學， 2007.
[2]任常興，吳宗之，李晉.基于風險分析的危險品道路運輸多目標Pareto最優選線[J].中國安全生產科學技術， 2008， 4（6）： 9-13.
[3]馬昌喜.不發達網絡環境下基于神經網絡的危險品公路運輸路徑決策[J].現代交通技術， 2009， 6（1）： 84-86.
[4]楊信豐，李引珍，何瑞春，馬昌喜.多屬性時間依賴網絡的城市危險品運輸路徑優化[J].中國安全科學學報， 2012， 22（9）： 103-108.
[5]項曙光， 焦巍， 孫曉巖，等. 基于模糊HSE評價的多目標反應路徑綜合方法[J]. 化工學報， 2013， 64（12）：4330-4334.
[6]馮艷紅， 劉建芹， 賀毅朝. 基于混沌理論的動態種群螢火蟲算法[J]. 計算機應用， 2013， 33（3）：796-799.
[7]Erkut E， Verter V. Modeling of transport risk for hazardous materials[J]. Operations Research， 1998， 46（3）： 625-642.
[8]Bhukya R， Somayajulu D V L N. 2-Jump DNA Search Multiple Pattern Matching Algorithm[J]. International Journal of Computer Science Issues， 2011， 8（3）.
[9]P. Serafini， Dynamic programming and minimum risk paths[J]， European Journal of Operational Research， 2006， 175（8）：224-237.
[10]Martin Trépanier， Marie-Hélène Leroux. Cross analysis of hazmat road accidents using multiple databases [J]. Accident Analysis Prevention， 2009， 41（3）： 1192-1189.
[11]Abbas Mahmoudabadi， Seyed Mohammad Seyedhosseini. Developing a chaotic pattern of dynamic Hazmat routing problem [J]. IATSS Research， 2014， 37（7）：110-118.
[12]Abbas Mahmoudabadi， Seyed Mohammad Seyedhosseini. Solving Hazmat Routing Problem in chaotic damage severity network under emergency environment[J]. Transport Policy， 2014， 36（5）： 34-45.
[13]任常興，吳宗之.危險品道路運輸風險分級指數法研究[J].安全與環境學報， 2006， 6（4）： 126-129.
[14]G.L.L. Reniers， W. Dullaert. A method to assess multi-modal Hazmat transport security vulnerabilities：Hazmat transport SVA [J]. Transport Policy， 2013， 28（6）： 103-113.
[15]李洪萍，裴玉龍.基于混沌理論的交通流短時預測模型[J].昆明理工大學學報：理工版， 2006， 31（5）：95-99.
[16]馮艷紅，劉建芹，賀毅朝.基于混沌理論的動態種群螢火蟲算法[J].計算機應用， 2013， 33（3）： 796-799.
[17]呂品.基于改進VRP模型的危險品配送路徑優化及其求解研究[J].中國安全生產科學技術， 2011， 7（11）： 87-91.
作者簡介：
關鍵詞：逆向工程；點云數據處理；CAD建模；汽車輪轂；實物模型數字化
中圖分類號：TP391 文獻標識碼：A 文章編號：1009-2374（2011）36-0068-02
逆向工程是消化吸收并改進先進技術的一系列工作方法和技術的總和，它是以設計方法學為指導，以現代設計理論方法技術為基礎，運用各種專業人員的工程設計經驗，知識和創新思維，對已有新產品進行解剖、深化和再創造，是已有設計的設計。逆向工程設計技術的應用對提高我國工業產品設計水平，縮短設計周期，增強我國產品在國際市場上的競爭力有著重要的意義。
一、實物模型數字化
實物模型數字化是逆向工程中很關鍵的一步，數字化模型能否準確反映實物模型的結構特點，直接影響后續的建模質量。因此，本文引入了COMET測量系統，COMET測量掃描系統是利用光柵投影法，通過非接觸方式獲得物體表面數字化點云數據，是一個快速而高精度的測量和掃描設備，使用COMET測量系統測量零件表面，操作流程：表面著色處理D確定測量方法D啟動軟硬件D調整測量角度和距離，并設置參數D掃描零件，獲取完整表面數據D數據輸出。
二、點云數據預處理
數字化階段獲得的點云數據應當經過適當的處理后才能用于后續的曲面建模。由于測量設備或是測量對象的原因，往往不能一次完成整個測量過程，需要將多個測量結果進行拼接才可獲得實物的整個數字化模型。
首先，在逆向掃描過程中，分塊掃描得到的點云數據可看成一個具體本身固定坐標系的實體。所以，逆向工程的點云數據對齊問題可以看作是不同三維實體的坐標變換問題，即根據事先指定的最優匹配算法，通過坐標變換，將分塊掃描得到的點云進行對齊。
其次，無論是使用接觸式測量還是非接觸式測量，在測量產品表面數據時，都會引入數據誤差，尤其是有尖銳邊的產品邊界附近的測量數據。因此，在利用點云數據重構模型前必須對點云進行過濾。
數據精簡也是逆向工程中的關鍵技術，伴隨非接觸式測量技術和測量設備的發展，我們可以很方便地獲得復雜形狀零件的表面數據。缺點是點云的數據量非常大，這就需要大量的存儲空間，同時在數據處理過程中，運行速度很慢，降低工作效率。因此，有必要在保持一定精度的前提下對點云進行精簡，去除大量多余的點，只保留能夠反映曲面形狀的點即可，這即是點云精簡過程。
三、CAD模型
三維CAD模型的重構是逆向工程的另一個核心和主要目的，是后續產品加工制造、快速成形、工程分析和產品再設計的基礎。三維CAD建模的理論，包括曲面建模方法、曲線和曲面的數學模型及擬合，應用CATIA軟件是實現曲面重構一個重要手段。
四、工程實例
當前，我國汽車工業飛速發展，越來越多的新車型被引入國內。同時，國內的汽車公司也在國外車型的基礎上大力自主研發設計新車型。因而，汽車的開發周期越來越短，汽車工業正逐漸由“大批量、單一車型”向“小批量，多種車型”制造模式轉變，在這種情況下，發展先進的制造技術，獲取或建立CAD模型具有重要的意義。
本文以研究汽車車輪轂蓋為例，將對某汽車車輪轂蓋進行數據掃描，并通過逆向工程手段實現的原有產品的逆向建模，以方便進一步的設計或模具制作，并可縮短其產品的開發周期。
（一）數據獲取
測量之前，首先應檢測輪轂蓋表面是否光澤，由于我們所測量的輪轂蓋表面的顏色是深灰色，表面顏色太深，反光能力差，應在其表面均勻地噴上白色反光噴劑，以便其有更好的反光效果。輪轂蓋曲面類型多，需多次測量，所以我們還需在被測物體的表面貼上參考點，這樣拼合點云的時候，多次測量得到的不同的點云就可以根據參考點實現自動拼合，將測量得到的數據以IGS格式輸入到CATIA軟件中。
（二）數據預處理
1．噪點刪除。由于掃描儀的誤差以及測量過程中人為誤差的存在，使得掃描最終得到的點云包含了大量的噪點，其將會嚴重影響后續的反求建模，又因為系統無法精確識別誤差的存在，所以需手動刪除。在CATIA中，利用“remove”工具進行刪除，如圖1（a）所示。
2．點云精簡。點云在消除了噪聲點后，其中仍包含了大量的冗余點，這些冗余點的存在不但增加了計算機的負荷，還影響數據處理和模型重建的速度，需在精度允許的范圍內采用一定的算法對其進行精簡。所以為了計算機運算速度的提高，CATIA提供公差球和弦高差兩種點云數據精簡方式。在此因曲面曲率變化原因選用弦高差精簡方式，其結果如圖1（b）所示。精簡后，點云的信息如下：
Number of Data Points： 59997
Units：mm
Min X=239.9893 Max X=505.7328
Min Y=-180.0058 Max Y=97.2953
Min Z=172.3559 Max Z=833.7889
3．網格化。在經過上述處理后便可以對其進行三角網格化，以便對其曲率進行分析，同時更好地觀察各種曲面的特征。
4．網格面曲率分析。點云分割是構建曲線、曲面的基礎，分塊方式直接影響后續的曲面構造方式、曲面的拼接和縫合效果。數據分塊分的好，將使曲面的重構變得簡單，可以得到高質量的曲面。
（三）輪轂蓋CAD模型重構
任何一個產品的模型建立之前，都必須有一定的基準，這樣才能建立產品準確的拓撲關系，也才能準確地進行后續的加工。對于此輪轂蓋同樣為了反求建模的準確性以及方便性，必須先建立其基準，即建立坐標系，并使其一坐標軸通過輪轂蓋的旋轉中心。
特征線的構建是曲面重構的基礎，也是最為關鍵的環節。由前面分析可知，此輪轂蓋主要由兩個旋轉曲面以及若干相同的掃描曲面組成。對于旋轉曲面，只要重構出它們的截面特征線即可。基本曲面重構完成之后，只需對其進行進一步的處理操作，如加厚、圓角等。最終進行表面質量的檢查。最后完成整體模型，并對其進行斑馬紋的檢查，如圖2所示，其質量足以滿足操作者的要求。
五、結語
在產品開發的今天，建立產品的數字化模型是產品設計的中心內容。在產品數字模型建立中，作為實現創新的手段，逆向工程技術的應用越來越受到重視。本文的研究工作豐富了產品造型設計的理論和方法，將促進逆向工程在產品設計中的應用和推廣。
參考文獻
[1] 王霄．逆向工程技術及其應用[M]．北京：化學工業出版社，2004．
[2] 金濤，童水光．逆向工程技術[M]．北京：機械工業出版社，2003．
[3] 許志龍．逆向工程中多視覺點云數據拼合技術[J]．設計與研究，2006，（7）．
[4] K H Lee H Woo，T Suk. Point Data Reduction Using 3D Grids[J]．International Journal of Advanced Manufacturing Technology，2001，（18）．
