面向不确定图的概率可达查询

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF数据库和XML数据库等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,已经有大量的针对不确定RDF和XML数据库的研究.文中使用可能世界语义模型构建不确定图,基于该模型,研究了概率可达查询(PR).处理PR查询是#P完全问题,对此文中首先给出一个基本随机算法,可快速地估算出可达概率,并且该值有很高的精确度.进一步,文中为随机算法引入条件分布(称为"条件随机算法"),采用图的不相交路径集和割集作为条件概率分布,因此改进的随机算法可准确地并且是在多项式时间内处理查询.最后基于真实不确定图数据的大量实验结果验证了文中的设计.     

An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 ^k n ³) time algorithm for this problem, significantly improving the previous algorithm of time for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n). A preliminary version of this paper was presented at The 10th Workshop on Algorithms and Data Structures (WADS 2007). This work was supported in part by the National Science Foundation under the Grants CCR-0311590 and CCF-0430683.     

一种基于点割集的感应失效节点容错算法

感应器失效节点通常发送错误数据,干扰全局信息判断,若转为睡眠状态则容易造成网络连通度下降,增加其他节点的路由转发负载.因此,对这些感应器失效节点的剩余能量进行利用,并进行自身估值,对于获取更准确的全局信息,保持网络负载平衡,具有重要的意义.提出一种基于点割集的感应失效节点容错算法,该算法基于数据相关图,筛选出与失效节点具有强数据相关性的点割集,然后利用所监听到的点割子集的观测量,进行正交估算,获取失效节点的最小均方误差估值.理论分析和实验结果表明,所提出的容错算法能较准确地估计失效点观测盲区,获取较完整的全局信息,同时由于算法使网络内的失效节点可以继续工作,保证了已有的网络负载平衡,维持原有的网络连通度.     

基于DOM树和递归X—Y分割算法的Zone树模型

在分析DOM树的基础上提出一种基于DOM树和递归X—Y分割算法,可以根据网页的几何布局生成Zone树模型。描述了将Zone树模型和递归X—Y算法应用到文献数据检索的优越性,给出构建Zone树模型的算法。该模型主要用于在线文献的数据提取,具有速度快、准确性高等特点,优于目前大多数浏览器所采用的DOM树结构。     

云化SFT下的径集域与割集域的重构与研究

为了克服原有SFT体系中径集域和割集域处理具有模糊性、随机性和离散性故障数据能力不足的问题,使用云模型和SFT相结合的方法来解决该问题。首先使用云模型云化SFT特征函数,得到云化特征函数,进而云化径集域和割集域,最终得到云化径集域和云化割集域。云化径集域和云化割集域没有严格的分界线,分布区域是通过云滴表示的。若云滴表示的元件/系统故障概率小于P_b,这些云滴存在的区域即为云化径集域;反之大于P_b的云滴存在的区域为云化割集域。通过实例分析了元件X₁和系统的云化径集域和云化割集域,得到了他们适合工作的环境因素变化范围组合。分析过程和结果表明云化径集域和云化割集域能克服原始故障数据的不确定性。     

Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph $G=(V,E)$ with edge-weights $w:E\to {\mathbb{R}}_{\ge 0}$ and vertex-weights $\eta :V\to {\mathbb{R}}_{+}$ are given. The goal is to find a vertex set $S\subseteq V$ with $|S|\le t$ while minimizing $w(S,V\backslash S)/\eta (S)$, where $w(S,V\backslash S)$ is the total weight of the edges with exactly one endpoint in S and $\eta (S)={\sum }_{v\in S}\eta (v)$. For this problem, we present a $(O(\log t),1+ϵ)$ factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when $t=n^{o(1)}$. We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.     

面向多种场景的视频对象自动分割算法

针对当前应用于视频对象分割的图割方法容易在复杂环境、镜头移动、光照不稳定等场景下鲁棒性不佳的问题,提出了结合光流和图割的视频对象分割算法.主要思路是通过分析前景对象的运动信息,得到单帧图像上前景区域的先验知识,从而改善分割结果.论文首先通过光流场采集视频中动作信息,并提取出前景对象先验区域,然后结合前景和背景先验区域建立图割模型,实现前景对象分割.最后为提高算法在不同场景下的鲁棒性,本文改进了传统的测地显著性模型,并基于视频本征的时域平滑性,提出了基于混合高斯模型的动态位置模型优化机制.在两个标准数据集上的实验结果表明,所提算法与当前其他视频对象分割算法相比,降低了分割结果的错误率,有效提高了在多种场景下的鲁棒性.     

基于激光雷达距离图像的道路边缘检测与跟踪

论述了将激光雷达的距离图像信息用于道路检测和跟踪。首先将扫描点进行聚类分析对道路边缘进行检测和对所检测的边缘进行最小二乘直线拟合,在成功检测道路边缘后,利用Kalman滤波对道路边缘进行跟踪。实验证明该算法具有检测准确且鲁棒性好的特点。     

Multiple piecewise constant with geodesic active contours (MPC-GAC) framework for interactive image segmentation using graph cut optimization

This paper proposes an improved variational model, multiple piecewise constant with geodesic active contour (MPC-GAC) model, which generalizes the region-based active contour model by Chan and Vese, 2001 [11] and merges the edge-based active contour by Caselles et al., 1997 [7] to inherit the advantages of region-based and edge-based image segmentation models. We show that the new MPC-GAC energy functional can be iteratively minimized by graph cut algorithms with high computational efficiency compared with the level set framework. This iterative algorithm alternates between the piecewise constant functional learning and the foreground and background updating so that the energy value gradually decreases to the minimum of the energy functional. The k-means method is used to compute the piecewise constant values of the foreground and background of image. We use a graph cut method to detect and update the foreground and background. Numerical experiments show that the proposed interactive segmentation method based on the MPC-GAC model by graph cut optimization can effectively segment images with inhomogeneous objects and background.