基于最小描述长度的图分割结构检测改进算法  

Improved Algorithm of Graph Partitioning Structure Detection Based on Minimum Description Length

作　　者：魏长宝[1] 姚汝贤[1] 

机构地区：[1]黄淮学院信息工程学院,河南驻马店463000

出　　处：《计算机工程》2016年第1期231-236,242,共7页Computer Engineering

基　　金：河南省科技攻关计划基金资助项目(122102210430)

摘　　要：针对现有图分割变化检测(GPCD)算法中易出现重复分割及忽略图形变化成本的不足,利用概率树表示图分割结构的概率模型。将GPCD问题转化为基于最小描述长度的树变化检测问题,利用树算法来求解GPCD问题。实验结果表明,在考虑变化成本的情况下,与GraphScope基准算法相比,TREE算法具有较低的虚警率和较高的检测精度。Aiming at the disadvantages of the existing Graph Partitioning Change Detection（GPCD） algorithm like repeated segmentation and ignoring change cost of images,it employs probabilistic trees to represent probabilistic models of graph partitioning structures.Then reduce GPCD into the issue of detecting changes of trees on the basis of the Minimum Description Length（MDL） principle.It proposes TREE algorithm for solving the GPCD problem.Simulation experimental results show that,by taking the cost of changes into consideration,TREE realizes significantly less False Alarm Rate（FAR） for change detection than the baseline method called GraphScope.And it is able to detect changes more accurately than GraphScope.

关 键 词：图分割变化检测 最小描述长度 概率树 变化成本 虚警率 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]