計算機科學技術

胡軍，王國胤，張清華

一種覆蓋粗糙模糊集模型

胡軍，王國胤，張清華

目的：信息粒化是人類處理信息的重要手段。通過信息粒化所得到的已知概念全體稱為近似空間。如何根據已知概念形成對目標概念的描述是概念認知中的一個重要問題。本文研究了覆蓋近似空間中模糊概念的近似，利用粗糙集理論給出了一種覆蓋粗糙模糊集模型，分析了這種模型的重要性質，探討了兩個不同覆蓋生成相同覆蓋粗糙模糊集的充要條件，研究了這種模型與現有其他模型間的關系，并給出了現有模型的應用前提。方法：由于知識粗糙性的原因，使得同一信息粒內的對象是不可分辨的。因而信息粒與目標模糊概念的隸屬關系由信息粒內的全體對象決定。其中，信息粒內對象與該模糊概念的最小隸屬度決定了隸屬關系的下界，而最大隸屬度決定了隸屬關系的上界。在覆蓋近似空間中，一個對象可能同時屬于多個信息粒。因此，一個對象與該模糊概念的隸屬關系由所有包含該對象的信息粒決定。其中，所有包含該對象的信息粒與該模糊概念的最大下界決定了隸屬關系的下界，而最小上界決定了隸屬關系的上界。從而，根據這種方法可以得到覆蓋近似空間中模糊概念的一種近似逼近。結果：這種覆蓋粗糙模糊集模型具有余正規性、正規性、下近似的收縮性、上近似的擴張性、對偶性、單調性和冪等性等性質。從分類的結果來看，該模型能有效避免已有模型中存在對象在下近似中不確定可分和上近似中不近似可分的問題。以信用卡審批為例，采用本文提出的覆蓋粗糙模糊集模型，可以根據用戶的受教育水平等信息預測用戶收入水平的區間。一個模糊概念的逼近程度與覆蓋近似空間的粒度呈單調性，即覆蓋近似空間的粒度越細，則相應的上、下近似越逼近該模糊概念。同時，任意模糊概念在兩個不同的覆蓋中有相同的覆蓋粗糙模糊集當且僅當這兩個覆蓋有相同的約簡，覆蓋近似空間的約減不改變模糊概念的上、下近似。現有兩種覆蓋粗糙模糊集模型是該模型的兩種極端情況。當覆蓋是一元的情況下，即論域中所有對象的最小描述有且僅有一個元素，這3種模型等價。結論：本文從規則的置信度出發，對覆蓋近似空間中模糊概念的近似進行了研究，具體分析了兩種覆蓋粗糙模糊集模型在上、下近似的定義上存在的不合理性。提出了一種新的覆蓋粗糙模糊集模型，修正了上、下近似定義的不合理性，并通過實例說明了本文所提模型的一個實際應用。證明了兩個覆蓋生成相同覆蓋粗糙模糊集的充要條件是它們有相同的約簡，為判斷兩個不同覆蓋近似空間的知識分辨能力是否相等提供了理論依據。并討論了3種模型在一般情況下的關系，發現已有兩種模型分別是兩種極端情況，以及它們應用于實際問題的前提條件是覆蓋是一元的。這些結論為覆蓋粗糙模糊集模型應用于決策為模糊的情形提供了理論基礎。

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

一種路徑敏感的靜態缺陷檢測方法

肖慶，宮云戰，楊朝紅，等

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

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

入選年份：2015

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

張向榮，騫曉雪，焦李成

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

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

入選年份：2015

物聯網資源尋址模型

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

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

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

入選年份：2015

前向隱私安全的低成本RFID認證協議

馬昌社

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

生器來構造滿足一定安全強度的前向隱私的RFID認證協議，也就是說如何構造兼容 EPCCIG2標準的前向8期馬昌社：前向隱私安全的低成本RFID認證協議1393隱私安全的RFID認證協議仍是一個值得進一步研究的問題。另一個值得研究的問題是：保證RFID協議一般ind隱私性的充分必要條件是什么？我們將進一步對這兩個問題進行研究。

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

入選年份：2015

基于開放網絡知識的信息檢索與數據挖掘

王元卓

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

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

改進的PMD距離圖像超分辨率重建算法

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

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

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