計算機(jī)科學(xué)技術(shù)

胡軍，王國胤，張清華

一種覆蓋粗糙模糊集模型

胡軍，王國胤，張清華

目的：信息?；侨祟愄幚硇畔⒌闹匾侄?。通過信息?；玫降囊阎拍钊w稱為近似空間。如何根據(jù)已知概念形成對目標(biāo)概念的描述是概念認(rèn)知中的一個重要問題。本文研究了覆蓋近似空間中模糊概念的近似，利用粗糙集理論給出了一種覆蓋粗糙模糊集模型，分析了這種模型的重要性質(zhì)，探討了兩個不同覆蓋生成相同覆蓋粗糙模糊集的充要條件，研究了這種模型與現(xiàn)有其他模型間的關(guān)系，并給出了現(xiàn)有模型的應(yīng)用前提。方法：由于知識粗糙性的原因，使得同一信息粒內(nèi)的對象是不可分辨的。因而信息粒與目標(biāo)模糊概念的隸屬關(guān)系由信息粒內(nèi)的全體對象決定。其中，信息粒內(nèi)對象與該模糊概念的最小隸屬度決定了隸屬關(guān)系的下界，而最大隸屬度決定了隸屬關(guān)系的上界。在覆蓋近似空間中，一個對象可能同時屬于多個信息粒。因此，一個對象與該模糊概念的隸屬關(guān)系由所有包含該對象的信息粒決定。其中，所有包含該對象的信息粒與該模糊概念的最大下界決定了隸屬關(guān)系的下界，而最小上界決定了隸屬關(guān)系的上界。從而，根據(jù)這種方法可以得到覆蓋近似空間中模糊概念的一種近似逼近。結(jié)果：這種覆蓋粗糙模糊集模型具有余正規(guī)性、正規(guī)性、下近似的收縮性、上近似的擴(kuò)張性、對偶性、單調(diào)性和冪等性等性質(zhì)。從分類的結(jié)果來看，該模型能有效避免已有模型中存在對象在下近似中不確定可分和上近似中不近似可分的問題。以信用卡審批為例，采用本文提出的覆蓋粗糙模糊集模型，可以根據(jù)用戶的受教育水平等信息預(yù)測用戶收入水平的區(qū)間。一個模糊概念的逼近程度與覆蓋近似空間的粒度呈單調(diào)性，即覆蓋近似空間的粒度越細(xì)，則相應(yīng)的上、下近似越逼近該模糊概念。同時，任意模糊概念在兩個不同的覆蓋中有相同的覆蓋粗糙模糊集當(dāng)且僅當(dāng)這兩個覆蓋有相同的約簡，覆蓋近似空間的約減不改變模糊概念的上、下近似?，F(xiàn)有兩種覆蓋粗糙模糊集模型是該模型的兩種極端情況。當(dāng)覆蓋是一元的情況下，即論域中所有對象的最小描述有且僅有一個元素，這3種模型等價。結(jié)論：本文從規(guī)則的置信度出發(fā)，對覆蓋近似空間中模糊概念的近似進(jìn)行了研究，具體分析了兩種覆蓋粗糙模糊集模型在上、下近似的定義上存在的不合理性。提出了一種新的覆蓋粗糙模糊集模型，修正了上、下近似定義的不合理性，并通過實例說明了本文所提模型的一個實際應(yīng)用。證明了兩個覆蓋生成相同覆蓋粗糙模糊集的充要條件是它們有相同的約簡，為判斷兩個不同覆蓋近似空間的知識分辨能力是否相等提供了理論依據(jù)。并討論了3種模型在一般情況下的關(guān)系，發(fā)現(xiàn)已有兩種模型分別是兩種極端情況，以及它們應(yīng)用于實際問題的前提條件是覆蓋是一元的。這些結(jié)論為覆蓋粗糙模糊集模型應(yīng)用于決策為模糊的情形提供了理論基礎(chǔ)。

來源出版物：軟件學(xué)報, 2010, 21(5): 968-977入選年份：2015

一種路徑敏感的靜態(tài)缺陷檢測方法

肖慶，宮云戰(zhàn)，楊朝紅，等

摘要：目的：軟件代碼中的缺陷是導(dǎo)致軟件故障和漏洞問題的主要原因。靜態(tài)缺陷檢測不運行被測程序，通過應(yīng)用各種靜態(tài)分析技術(shù)來發(fā)現(xiàn)程序中的缺陷。靜態(tài)缺陷檢測是一個不可判定問題，提高精度是靜態(tài)缺陷檢測的核心。提高精度包括兩個方面：減少誤報和減少漏報。本文在傳統(tǒng)數(shù)據(jù)流分析的基礎(chǔ)上，采用路徑敏感的靜態(tài)缺陷檢測技術(shù)，探索減少靜態(tài)缺陷檢測誤報的方法。方法：采用路徑敏感的靜態(tài)缺陷檢測技術(shù)，減少靜態(tài)缺陷檢測的誤報。首先，利用有限狀態(tài)機(jī)來描述程序的“時序安全屬性”。在靜態(tài)缺陷檢測過程中，計算每個程序位置上狀態(tài)機(jī)的可能屬性狀態(tài)集合，如果可能屬性狀態(tài)集合中包含error狀態(tài)即報告一個潛在的缺陷。其次，引入屬性狀態(tài)條件來記錄屬性狀態(tài)所經(jīng)歷的路徑信息。屬性狀態(tài)條件采用變量的抽象取值范圍表示，通過屬性狀態(tài)條件中的變量抽象取值范圍為空來判斷不可達(dá)路徑。最后，在所有控制流匯合節(jié)點上，將相同屬性狀態(tài)的屬性狀態(tài)條件進(jìn)行合并以避免完整路徑分析的路徑組合指數(shù)爆炸問題。該方法是一種多項式復(fù)雜度的路徑敏感缺陷檢測方法。結(jié)果：為分析路徑敏感算法消除誤報的效果，針對路徑不敏感（傳統(tǒng)數(shù)據(jù)流分析）和本文提出的路徑敏感方法進(jìn)行缺陷檢測對比實驗1。分析掃描的對象為10個大型Java開源軟件（選取標(biāo)準(zhǔn)為sourceforge排名靠前且能編譯通過）。掃描的目標(biāo)為資源泄漏和空句柄引用這兩類缺陷，并對掃描結(jié)果進(jìn)行了人工確認(rèn)。采用路徑不敏感方法總體分析時間為2099 s，路徑敏感方法總體分析時間為 2284 s，總體分析時間增加了8.81%。采用路徑不敏感方法的誤報數(shù)為 486，采用路徑敏感方法的誤報數(shù) 403，誤報數(shù)減少了 17.08%。Das等人提出一種在屬性狀態(tài)上增加程序執(zhí)行符號狀態(tài)信息并利用這些執(zhí)行符號狀態(tài)信息來排除不可達(dá)路徑的多項式復(fù)雜度路徑敏感方法。在他們實現(xiàn)的工具 ESP中，采用常量傳播格來表示執(zhí)行符號狀態(tài)信息。而在我們實現(xiàn)的工具 DTS中采用抽象取值范圍來表示變量取值信息。針對常量傳播格表示和抽象取值范圍表示進(jìn)行了缺陷檢測對比實驗 2，分析掃描對象及目標(biāo)與實驗 1相同。采用常量傳播格表示的分析時間為 2214 s，采用抽象取值范圍表示的分析時間為 2284 s。采用常量傳播格表示比采用抽象取值范圍表示多了7個誤報。結(jié)論：本文討論了路徑不敏感造成靜態(tài)分析不精確的原因，并提出了一種多項式復(fù)雜度的路徑敏感缺陷檢測方法。相比路徑不敏感分析算法，本文提出的路徑敏感分析算法，只增加較少的分析時間，但能夠有效地減少誤報。研究選擇哪些控制流匯合節(jié)點和哪些屬性狀態(tài)進(jìn)行屬性狀態(tài)條件合并，可以更好地求得復(fù)雜度和精度的平衡。

來源出版物：軟件學(xué)報, 2010, 21(2): 209-217

入選年份：2015

基于免疫譜聚類的圖像分割

張向榮，騫曉雪，焦李成

摘要：目的：隨著圖像數(shù)據(jù)復(fù)雜度的增加，傳統(tǒng)圖像分割方法已不能滿足實際應(yīng)用的需求，本文主要針對經(jīng)典譜聚類算法中采用的k-均值算法易陷入局部最優(yōu)和對初始化敏感的缺點，提出了用免疫克隆聚類算法取代k-均值算法的改進(jìn)譜聚類方法，并將其用于圖像分割。方法：免疫譜聚類算法結(jié)合譜聚類算法和免疫聚類算法，利用譜聚類的維數(shù)縮減特性獲得數(shù)據(jù)在映射空間的分布，在此基礎(chǔ)上構(gòu)造了一種新免疫克隆聚類算法用于在映射空間中對樣本進(jìn)行聚類。針對合成紋理圖像和SAR圖像進(jìn)行分割，首先提取一副圖像的紋理特征，采用基于灰度共生矩陣的紋理特征提取方法和非下采樣三級小波分解可以獲得圖像的紋理信息，這樣每一個像素用一個m維的特征向量來表示。然后利用 Nystr?ms逼近方法來降低譜聚類算法的運算復(fù)雜度。通過譜聚類算法將其映射到一個線性測度空間得到（n×k）的樣本，再通過免疫克隆聚類尋找這些（n×k）樣本的最優(yōu)聚類中心，最后將每一個樣本分類到離它最近的聚類中心所在的類別中去。結(jié)果：在4個UCI數(shù)據(jù)集的聚類結(jié)果可以看出，免疫譜聚類算法的錯誤率比對比算法：NJW算法和k-均值聚類有大幅度的降低，同時免疫譜聚類算法對尺度參數(shù)的魯棒性也優(yōu)于 NJW 算法。在合成紋理圖像和SAR圖像分割中，對圖像中的每個像素，首先對其進(jìn)行特征提取，由于基于灰度共生矩陣的統(tǒng)計量和基于非下采樣小波分解的能量特征在紋理分析中表現(xiàn)出良好的特性，因此，對圖像提取基于灰度共生矩陣的 12維特征和基于 3層非下采樣小波能量的 10維特征，構(gòu)成 22維特征向量。在聚類前對特征向量進(jìn)行歸一化處理。為了比較，分別采用k-均值算法和 NJW算法以及本文提出的免疫譜聚類算法對圖像進(jìn)行分割。在合成紋理圖像上的結(jié)果表明：無論從視覺角度還是相對于理想分割的錯誤率，新方法都優(yōu)于k-均值算法和NJW算法。在SAR圖像上的結(jié)果表明：新方法的分割結(jié)果在區(qū)域一致性和邊界的準(zhǔn)確定位均優(yōu)于k-均值聚類和 NJW的結(jié)果，能夠獲得SAR圖像區(qū)域的正確劃分。結(jié)論：譜聚類算法可處理任意形狀數(shù)據(jù)聚類問題，免疫克隆選擇具有對初始化不敏感，能夠快速尋找到全局最優(yōu)解的特性，結(jié)合兩者優(yōu)勢，提出了免疫譜聚類算法用于圖像分割。通過譜映射為后續(xù)的免疫克隆聚類提供低維而緊致的輸入，而免疫克隆聚類算法具有快速收斂到全局最優(yōu)并且對初始化不敏感的特性，從而可以獲得良好的聚類結(jié)果。結(jié)果表明，該算法降低了特征維數(shù)，且提高了圖像分割精度，在將其用于圖像分割時，采用了Nystr?m逼近策略來降低算法復(fù)雜度。在合成紋理圖像和SAR圖像的分割實驗中驗證了免疫譜聚類算法用于圖像分割的有效性。

來源出版物：軟件學(xué)報, 2010, 21(9): 2196-2205

入選年份：2015

物聯(lián)網(wǎng)資源尋址模型

孔寧，李曉東，羅萬明，等

摘要：目的：物聯(lián)網(wǎng)是 RFID（radio frequency identification，射頻識別）技術(shù)與互聯(lián)網(wǎng)結(jié)合而成的新興產(chǎn)物，具有和互聯(lián)網(wǎng)相似的資源尋址需求。目前，物聯(lián)網(wǎng)資源尋址的研究仍處于起步階段，基本上直接沿用互聯(lián)網(wǎng)現(xiàn)有的資源尋址技術(shù)，而未考慮解決多種物品編碼標(biāo)準(zhǔn)共存而引起的尋址沖突等物聯(lián)網(wǎng)特有的資源尋址問題。本文提出物聯(lián)網(wǎng)資源尋址的通用層次模型，為解決物聯(lián)網(wǎng)資源尋址的特有問題提供理論模型依據(jù)。方法：在分析物聯(lián)網(wǎng)尋址特性的基礎(chǔ)上，對于互聯(lián)網(wǎng)資源尋址模型進(jìn)行擴(kuò)展，首先對資源名稱的類型進(jìn)行了細(xì)化，提出了資源名稱可以劃分為顯性和隱性兩種類型，并且隱性資源名稱可以通過相應(yīng)的信息轉(zhuǎn)換為滿足尋址系統(tǒng)的顯性資源名稱；其次對尋址系統(tǒng)的輸出做了擴(kuò)展，將資源地址擴(kuò)展為生成資源地址所必須的相關(guān)地址信息，通過此擴(kuò)展，尋址系統(tǒng)的輸出將不僅限于資源地址本身，還可以是包含生成資源地址的信息，從而為隱性資源名稱到顯性資源名稱的轉(zhuǎn)換提供了條件。通過分析物聯(lián)網(wǎng)資源尋址特性，對互聯(lián)網(wǎng)資源尋址的層次迭代模型進(jìn)行擴(kuò)展。結(jié)果：通過分析，在隱性資源名稱為空的情況下，資源地址信息等同于該層次的顯性資源名稱，直接作為該層次尋址系統(tǒng)的輸入，物聯(lián)網(wǎng)資源尋址的通用層次模型等價于互聯(lián)網(wǎng)資源尋址的層次迭代模型。因此，互聯(lián)網(wǎng)資源尋址的層次迭代模型是物聯(lián)網(wǎng)資源尋址的通用層次模型的簡化模型，而物聯(lián)網(wǎng)資源尋址的通用層次模型是基于互聯(lián)網(wǎng)資源尋址的層次迭代模型的擴(kuò)展模型。物聯(lián)網(wǎng)資源尋址的通用層次模型相比基于互聯(lián)網(wǎng)資源尋址的層次迭代模型，僅在尋址層次中增加了隱性資源名稱到顯性資源名稱的轉(zhuǎn)換操作，而該操作只涉及字符串匹配、替換等簡單運算，其帶來的時間消耗相對于尋址層次中與尋址系統(tǒng)交互而建立網(wǎng)絡(luò)連接的消耗而言可忽略不計。因此，物聯(lián)網(wǎng)資源尋址的通用層次模型在與基于互聯(lián)網(wǎng)資源尋址的層次迭代模型保持相同量級復(fù)雜性的條件下，實現(xiàn)了功能上的擴(kuò)展?；谖锫?lián)網(wǎng)資源尋址的通用層次模型，結(jié)合物聯(lián)網(wǎng)資源尋址特性，對互聯(lián)網(wǎng)資源尋址的應(yīng)用結(jié)構(gòu)模型進(jìn)行擴(kuò)展，提出了物聯(lián)網(wǎng)資源尋址的應(yīng)用結(jié)構(gòu)模型。該應(yīng)用結(jié)構(gòu)模型劃分為物品標(biāo)準(zhǔn)尋址層、物品編碼尋址層、物品發(fā)現(xiàn)尋址層、物品信息尋址層以及物理地址尋址層等五個層次，其中物品標(biāo)準(zhǔn)尋址層為物聯(lián)網(wǎng)資源尋址領(lǐng)域特有層次，并提出物品標(biāo)準(zhǔn)尋址層中物品編碼標(biāo)準(zhǔn)識別碼的概念。物品編碼標(biāo)準(zhǔn)識別碼在物品標(biāo)準(zhǔn)尋址層的資源尋址解析為物聯(lián)網(wǎng)資源尋址支持任意物品編碼標(biāo)準(zhǔn)的物品編碼提供基礎(chǔ)。結(jié)論：通過分析物聯(lián)網(wǎng)資源尋址特性，對互聯(lián)網(wǎng)資源尋址的層次迭代模型進(jìn)行擴(kuò)展。提出物聯(lián)網(wǎng)資源尋址的通用層次模型，為解決由多種物品編碼標(biāo)準(zhǔn)共存而引起的物聯(lián)網(wǎng)資源尋址的特有問題提供理論模型依據(jù)。通過對其功能性實現(xiàn)，驗證了通用層次模型的有效性及可行性。為研究物聯(lián)網(wǎng)資源尋址的相關(guān)問題提供了理論依據(jù)，便于今后提出合理可行的物聯(lián)網(wǎng)資源尋址解決方案。

來源出版物：軟件學(xué)報, 2010, 21(7): 1657-1666

入選年份：2015

前向隱私安全的低成本RFID認(rèn)證協(xié)議

馬昌社

摘要：標(biāo)簽成本和隱私安全是制約RFID技術(shù)在物聯(lián)網(wǎng)中得到廣泛應(yīng)用的主要因素。因此，設(shè)計隱私安全且標(biāo)簽生產(chǎn)成本低的RFID認(rèn)證協(xié)議是學(xué)術(shù)界和工業(yè)界共同追求的目標(biāo)。針對這一目標(biāo)，利用只需要實現(xiàn)偽隨機(jī)數(shù)發(fā)生器的標(biāo)簽構(gòu)造了簡單的 RFID認(rèn)證協(xié)議SFP，并在標(biāo)準(zhǔn)模型下證明了SFP協(xié)議具有前向隱私安全性。為了說明在保證前向隱私的條件下SFP協(xié)議的標(biāo)簽生產(chǎn)成本低，證明了標(biāo)簽具有產(chǎn)生偽隨機(jī)數(shù)的能力是保證RFID前向隱私的必要條件。因此，與現(xiàn)有RFID協(xié)議相比較，SFP協(xié)議不但計算和通信效率高，而且同時保證了前向隱私安全和低標(biāo)簽生產(chǎn)成本，實現(xiàn)了RFID技術(shù)低標(biāo)簽成本和高隱私安全的結(jié)合安全和低成本是工業(yè)界對RFID技術(shù)的兩個基本要求，但又是兩個互相沖突的要求。低成本的RFID不能保證安全性，滿足一定安全要求的RFID標(biāo)簽成本較高。能否設(shè)計出既具有隱私安全又具有低標(biāo)簽成本的RFID認(rèn)證協(xié)議呢？這是人們急需解決的問題。本文針對這個問題研究了前向隱私安全的RFID認(rèn)證協(xié)議的設(shè)計和標(biāo)簽計算復(fù)雜度。設(shè)計了一個優(yōu)化的 RFID認(rèn)證協(xié)議 SFP。與其它協(xié)議相比較，SFP協(xié)議不但簡單、高效、具有標(biāo)準(zhǔn)模型下的可證明前向隱私安全，而且對標(biāo)簽的計算要求低，從而協(xié)議SFP中的標(biāo)簽具有較低的生產(chǎn)成本。同時，歸納出了保證 RFID系統(tǒng)前向隱私的充分必要條件，解決了前向隱私和標(biāo)簽計算能力（也就是生產(chǎn)成本）之間的關(guān)系問題。本文研究豐富了RFID隱私安全理論，為工業(yè)界生產(chǎn)具有前向隱私安全的RFID系統(tǒng)提供了指導(dǎo)。本文結(jié)論表明：保證RFID前向隱私的充分必要條件是標(biāo)簽具有計算偽隨機(jī)數(shù)發(fā)生器的能力。而EPCCIG2標(biāo)準(zhǔn)中的標(biāo)簽具有16 bits的偽隨機(jī)數(shù)發(fā)生器，如何根據(jù)這種輸出短的偽隨機(jī)數(shù)發(fā)

生器來構(gòu)造滿足一定安全強(qiáng)度的前向隱私的RFID認(rèn)證協(xié)議，也就是說如何構(gòu)造兼容 EPCCIG2標(biāo)準(zhǔn)的前向8期馬昌社：前向隱私安全的低成本RFID認(rèn)證協(xié)議1393隱私安全的RFID認(rèn)證協(xié)議仍是一個值得進(jìn)一步研究的問題。另一個值得研究的問題是：保證RFID協(xié)議一般ind隱私性的充分必要條件是什么？我們將進(jìn)一步對這兩個問題進(jìn)行研究。

來源出版物：計算機(jī)學(xué)報, 2011, 34(8): 1387-1398

入選年份：2015

基于開放網(wǎng)絡(luò)知識的信息檢索與數(shù)據(jù)挖掘

王元卓

摘要：目的：網(wǎng)絡(luò)大數(shù)據(jù)是指“人、機(jī)、物”三元世界在網(wǎng)絡(luò)空間（cyberspace）中交互、融合所產(chǎn)生并在互聯(lián)網(wǎng)上可獲得的大數(shù)據(jù)。這些數(shù)據(jù)具有多源異構(gòu)、交互性、時效性、社會性、突發(fā)性和高噪聲等特點，不但非結(jié)構(gòu)化數(shù)據(jù)多，而且數(shù)據(jù)的實時性強(qiáng)。網(wǎng)絡(luò)大數(shù)據(jù)背后蘊含著豐富的、復(fù)雜關(guān)聯(lián)的知識。建立面向開放網(wǎng)絡(luò)的知識庫，是獲取網(wǎng)絡(luò)大數(shù)據(jù)中的豐富知識的有效手段。本文分析了主流開放網(wǎng)絡(luò)知識庫的構(gòu)建的主要特點，論述了開放網(wǎng)絡(luò)知識庫在信息檢索和知識挖掘方面的主要作用，并介紹了當(dāng)前知名系統(tǒng)和應(yīng)用的情況。最后對開放網(wǎng)絡(luò)知識庫的研究與應(yīng)用面臨的挑戰(zhàn)和未來研究的重點進(jìn)行了展望。方法和結(jié)果：在開放網(wǎng)絡(luò)知識庫構(gòu)建方面，本文從開放網(wǎng)絡(luò)知識庫的構(gòu)建、多源知識的融合以及知識庫的更新3個方面，對當(dāng)前國內(nèi)外主要的開放網(wǎng)絡(luò)庫進(jìn)行了比較。具體的講，本文主要論述了開放網(wǎng)絡(luò)知識庫的自動構(gòu)建的兩種方法，即有監(jiān)督的構(gòu)建方法和半監(jiān)督的構(gòu)建方法。列舉了包括KnowItAll，TextRunner，NELL，Probase這些典型的通過半監(jiān)督的構(gòu)建方法構(gòu)建知識庫的具體流程。在多源知識的融合方面，本文介紹了以YAGO和Probase為代表的、建立在機(jī)器學(xué)習(xí)算法之上的、可擴(kuò)展的融合方法。在知識庫的更新方面，本文介紹了以 NELL和 YAGO2為代表的兩類知識庫更新方法，即基于知識庫構(gòu)建人員的更新和基于知識庫存儲的時空信息的更新。在基于開放網(wǎng)絡(luò)知識庫的信息檢索方面，本文從用戶意圖理解、查詢擴(kuò)展、語義問答三個方面展開論述，并就線索挖據(jù)、關(guān)系推理以及關(guān)系和屬性預(yù)測這3個基于開放網(wǎng)絡(luò)知識庫數(shù)據(jù)挖掘方向進(jìn)行了回顧。最后，本文分析比較了兩類基于開放網(wǎng)絡(luò)知識庫的代表性的智能搜索引擎，即人物關(guān)系搜索和知識關(guān)系搜索的特點。并就流行趨勢分析、排名關(guān)鍵詞分析、統(tǒng)計分析這3類代表性的商業(yè)情報分析系統(tǒng)進(jìn)行了論述。結(jié)論：基于開放網(wǎng)絡(luò)大數(shù)據(jù)的知識庫為人們深入利用網(wǎng)絡(luò)大數(shù)據(jù)的價值提供有效的途徑。目前，雖然在國內(nèi)外已經(jīng)有了一些以開放網(wǎng)絡(luò)數(shù)據(jù)為基礎(chǔ)的知識庫，并興起了一些新興的應(yīng)用，但無論知識庫的構(gòu)建、更新，還是應(yīng)用都還不能完美地滿足人們的應(yīng)用需求，也就意味著每個方向都有極具挑戰(zhàn)性的工作。本文從5個方面，即開放網(wǎng)絡(luò)知識庫的創(chuàng)建和更新中融入群體智慧，開放網(wǎng)絡(luò)知識庫的實時感知與自動更新，通用知識庫與領(lǐng)域知識庫相結(jié)合實現(xiàn)有效跨庫映射，實現(xiàn)知識庫的跨語言融合，通過計算實現(xiàn)對潛在知識的推斷和未來趨勢的預(yù)測對下一步的工作進(jìn)行了展望。

來源出版物：計算機(jī)研究與發(fā)展, 2015, 52(2): 456-474入選年份：2015

改進(jìn)的PMD距離圖像超分辨率重建算法

張旭東，沈玉亮，胡良梅，等

摘要：目的：在當(dāng)今計算機(jī)視覺和多媒體等應(yīng)用領(lǐng)域，目標(biāo)到傳感器的距離獲取技術(shù)取得了不少顯著成效。PMD（photonic mixer device）相機(jī)是一款基于 TOF（time-of-flight）技術(shù)的主動式三維成像系統(tǒng)，該相機(jī)能夠以視頻幀速率實時地獲得距離圖像和幅度圖像。距離圖像通過發(fā)射信號和反射信號之間的相位偏移計算得到，幅度圖像通過每個像素點位置的反射信號幅度信息得到。由于其低成本和高幀率，被廣泛用于三維可視化、模式識別、計算機(jī)視覺和多媒體等領(lǐng)域。然而，它的主要缺點是分辨率低，并存在較大的隨機(jī)噪聲，這些缺陷限制了 PMD相機(jī)的應(yīng)用。傳統(tǒng)的非連續(xù)自適應(yīng)馬爾可夫隨機(jī)場（discontinuity adaptive markov random field，DAMRF）模型的超分辨率圖像重建方法，不能有效地對距離圖像濾波去噪，距離圖像分辨率不能得到有效地提高。針對此問題，本文提出了一種改進(jìn)的DAMRF模型的超分辨率重建方法，以此來提高距離圖像的分辨率，以去除距離圖像的隨機(jī)噪聲。方法：本文在傳統(tǒng)DAMR模型方法的基礎(chǔ)上，實現(xiàn)了一種改進(jìn)的DAMRF模型的超分辨率重建方法，該方法不僅保留了雙邊濾波器的特點，而且結(jié)合了貝葉斯框架下的最大后延概率（MAP）估計理論。首先利用雙邊濾波器由空間項和距離項乘積組成的特點，引入新的懲罰函數(shù)，構(gòu)建改進(jìn)DAMRF模型的能量函數(shù)，該能量函數(shù)由距離項和空間項組成，這兩項可以用高斯函數(shù)表示。距離項采用自適應(yīng)函數(shù)形式，描述兩個像素點在光度上的相似性，并且能夠?qū)ο噜徬袼亻g的梯度影響進(jìn)行自適應(yīng)調(diào)整，從而有效地保持圖像邊緣連續(xù)性?？臻g項描述了距離圖像像素點之間在幾何空間上的鄰近關(guān)系。然后引入調(diào)制信號幅度的平方作為可信度，將其作為權(quán)值對傳統(tǒng)DAMRF模型中能量函數(shù)的距離項進(jìn)行自適應(yīng)加權(quán)，用具有較高可信度像素距離值代替具有較低可信度距離像素值，從而增加每個像素點在平滑過程中的權(quán)值。當(dāng)鄰域內(nèi)的像素點與中心點像素點的距離差值較大時，這個點位于圖像的邊緣，其在平滑過程中所占的權(quán)值也較低，從而該算法有效地增強(qiáng)了距離圖像的邊緣信息，能夠很好地保持圖像的邊緣連續(xù)。最后在貝葉斯框架下，利用最大后驗概率（MAP）估計理論，確定改進(jìn)DAMRF模型的表達(dá)式，同時采用基于光流估計的圖像配準(zhǔn)方法對低分辨率的距離圖像進(jìn)行配準(zhǔn)，把獲得的低分辨率距離圖像之間的運動參數(shù)和初始高分辨率圖像應(yīng)用于GNC（graduated non-convexity）優(yōu)化算法中，進(jìn)行迭代求解，從而獲得重建圖像的最優(yōu)近似解。為了避免運動視差的影響，通常選擇連續(xù)幀或接近連續(xù)的序列作為測試圖像，本文實驗利用PMD相機(jī)捕捉的4幅低分辨率圖像作為測試圖像。同時，為了驗證本文方法的有效性，采用信噪比（SNR）和均方根誤差（RMSE）作為重建圖像性能的評價指標(biāo)。結(jié)果：本文方法不僅提高了距離圖像的空間分辨率，而且能夠有效地濾波去除距離圖像存在的隨機(jī)噪聲，同時克服重建圖像的邊緣模糊，以有效增強(qiáng)距離圖像的邊緣信息，從而較好地保持了圖像邊緣的連續(xù)性。對于定性視覺效果比較，重建圖像的整體效果也得到一定的提高。對于定量結(jié)果比較，本文方法獲得重建圖像的信噪比（SNR）和均方根誤差（RMSE）都有較好的改善，信噪比平均提升約3.848 dB，均方根誤差平均減少約 0.002。結(jié)論：無論是在定性視覺效果還是在定量性能評價方面，本文提出的改進(jìn)的DAMRF模型的超分辨率重建方法的重建結(jié)果均優(yōu)于傳統(tǒng)DAMRF模型的超分辨率方法，能夠很好地彌補(bǔ)PMD相機(jī)空間分辨率低、隨機(jī)噪聲大的缺陷。采用GNC的優(yōu)化算法避免了局部最小值的問題，從而獲得重建圖像的最優(yōu)近似解。但是不同正則化參數(shù)對距離圖像重建結(jié)果具有重要影響，因此通過建模自適應(yīng)選擇正則化參數(shù)可以進(jìn)一步提高算法的魯棒性。

來源出版物：中國圖象圖形學(xué)報, 2012, 17(4): 480-486入選年份：2015