计算机科学技术

胡军，王国胤，张清华

一种覆盖粗糙模糊集模型

胡军，王国胤，张清华

目的：信息粒化是人类处理信息的重要手段。通过信息粒化所得到的已知概念全体称为近似空间。如何根据已知概念形成对目标概念的描述是概念认知中的一个重要问题。本文研究了覆盖近似空间中模糊概念的近似，利用粗糙集理论给出了一种覆盖粗糙模糊集模型，分析了这种模型的重要性质，探讨了两个不同覆盖生成相同覆盖粗糙模糊集的充要条件，研究了这种模型与现有其他模型间的关系，并给出了现有模型的应用前提。方法：由于知识粗糙性的原因，使得同一信息粒内的对象是不可分辨的。因而信息粒与目标模糊概念的隶属关系由信息粒内的全体对象决定。其中，信息粒内对象与该模糊概念的最小隶属度决定了隶属关系的下界，而最大隶属度决定了隶属关系的上界。在覆盖近似空间中，一个对象可能同时属于多个信息粒。因此，一个对象与该模糊概念的隶属关系由所有包含该对象的信息粒决定。其中，所有包含该对象的信息粒与该模糊概念的最大下界决定了隶属关系的下界，而最小上界决定了隶属关系的上界。从而，根据这种方法可以得到覆盖近似空间中模糊概念的一种近似逼近。结果：这种覆盖粗糙模糊集模型具有余正规性、正规性、下近似的收缩性、上近似的扩张性、对偶性、单调性和幂等性等性质。从分类的结果来看，该模型能有效避免已有模型中存在对象在下近似中不确定可分和上近似中不近似可分的问题。以信用卡审批为例，采用本文提出的覆盖粗糙模糊集模型，可以根据用户的受教育水平等信息预测用户收入水平的区间。一个模糊概念的逼近程度与覆盖近似空间的粒度呈单调性，即覆盖近似空间的粒度越细，则相应的上、下近似越逼近该模糊概念。同时，任意模糊概念在两个不同的覆盖中有相同的覆盖粗糙模糊集当且仅当这两个覆盖有相同的约简，覆盖近似空间的约减不改变模糊概念的上、下近似。现有两种覆盖粗糙模糊集模型是该模型的两种极端情况。当覆盖是一元的情况下，即论域中所有对象的最小描述有且仅有一个元素，这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