论文部分内容阅读
符号网络是指边具有正或负符号属性的网络,其中正负边分别代表积极和消极关系。消极关系普遍存在于信息、生物和社会领域,为人们研究态度预测、用户特征分析以及聚类等方向提供了重要的应用价值。近年来涌现出多个符号图聚类准则,它们在许多领域中取得了成功应用,并验证了负边带来的附加价值。然而,如何理解符号图聚类与典型无符号图聚类的联系与区别,如何统一多个符号图聚类,以及如何针对应用场景来构建符号网络,这些问题都还未得到深入研究。本文面向图像分割这一实际问题,以该领域中成功应用的典型聚类准则--规范化割(Normalized cut,简称Ncut)为分析对象,对上述疑问展开讨论。图像是一类半结构化数据,传统的图聚类算法以非负权重来表达像素点(块)之间的相似性。实际上,消极关系也存在于图像数据分析中,不同分割区域的像素点(块)对则为互斥关系,可以用负边来表征这种关系。相比无符号图,引入负边的符号图更具表达能力。本文利用符号网络聚类来解决图像的半监督分割问题,研究了符号网络的构建,并对符号图聚类展开了详细分析。本文的主要工作包括以下几个方面。1.对比分析了符号图上的规范化割。首先,对比分析无符号网络上的半监督规范化割准则和符号图规范化割的异同,并给出了它们的统一定义形式。然后,针对符号规范化割提出了符号网络聚类的四个目标,并定义了广义的符号规范化割。最后在划线形式的交互式图像分割问题上进行实验分析,结果表明:i)图的定义方式会对聚类性能产生显著影响,规范化形式也会对结果产生一定影响;ii)同时实现最小化组内不相似性和最大化组内相似性两个目标,能较好地进行聚类,仅考虑最小化组间相似性也能为聚类提供有效的指导。2.针对图像分割问题,分别在两种先验形式下构建了符号网络,并尝试结合MRF正则化项来改进符号规范化割。分别在touch交互形式与显著性检测情形下构建了符号网络,并利用核割算法优化了MRF约束下的符号规范化割。在图像数据上进行分割实验,结果表明:纳入MRF约束能提升符号规范化割的图像分割效果;两种先验形式下的符号网络的构建方式都是有效的,并且交互式分割结果要略优于基于显著性检测的自动分割。综上所述,本文尝试面向图像数据来构建符号网络,通过对网络聚类准则的分析研究来实现图像的半监督分割。不仅为半监督聚类提供了新的方法,也扩充了符号网络的应用。