一种基于Graph Cuts的SAR图像分割方法

在最小化由马尔科夫随机场(MRF)图像分割模型建立的能量函数方面,基于Graph Cuts的alpha-expansion是一种比较有效的算法.但是,由此算法构建的s/t图中边的数目非常多,运算速度很慢.为了减少alpha-expansion算法的计算量,本文在标号为alpha的像素向其它像素膨胀的过程中,先隔离非alpha类间的联系,而只考虑alpha类与非alpha类之间的关系,从而避免了alpha-expansion算法需要构造辅助结点的问题,减少了s/t图中边的数目,提高了算法的计算效率.因放松了非alpha类间的关系对alpha膨胀的约束,使得算法可以更容易得跳出能量函数的局部极小点而获得更优的分割结果.实验中将改进的算法与传统的基于Graph Cuts的算法做了对比,显示了新算法在运算时间和最小化能量方面的有效性.     

基于Apriori图挖掘算法的优化及其在3D构造解析的应用

基于Apriori的图挖掘(Apriori-based Graph Mining,AGM)算法结构简单,以递归统计为基础,但在面临庞大图数据集时,由于存在子图同构问题,在生成候选子图时容易产生很多冗余子图,增大了计算时间的开销。因此在AGM算法基础上提出一种改进方法,通过增加约束来减少候选子图生成数量,同时引入三次元坐标对图的顶点间的距离进行计算,并归结到边的标识当中,以处理三维图结构数据。通过改进算法对化学化合物进行分析,描述其三维化学结构以及生理活性上的相互关系,并测试了不同条件下改进方法的时间开销,实验结果表明在边标识数较多的情况下改进算法比原算法缩短了计算时间,提高了效率。     

一种基于流量需求的动态频谱分配算法

感知无线电是一个解决当前频谱资源紧缺情况的有效手段,其中动态频谱分配技术是一个非常重要的环节.文章首先建立了基于冲突图的需求分配模型,基于此模型提出了一种基于用户需求的动态频谱分配算法,在传统标签机制基础上增加了对感知用户随时间改变的频谱需求的支持.试验结果表明,当每个感知用户对频谱的需求随着时间的变化而变化并且为有限值的情况下,该算法能保证较好的公平性和提供较高的分配效率.     

Web日志挖掘中3G WAP子网的获取研究

随着3G时代的到来,手机上网已逐步普及,由于手机屏幕较小及上网带宽限制,需要为手机访问者提供只需保留原Web站点主干分支的WAP子网。WWW上用户的访问路径信息会被记录在Web服务器的日志记录中,分析这些日志并挖掘出用户的主要行为模式,可以提取出Web网站被频繁访问的主干部分。首先将原始日志序列转化成用户访问路径会话集UVPSD,然后通过约束的加权网站结构图WWSSG,最终实现了此Web站点的频繁主干子网的发现。在上海社区网上采用此算法提取出的3G WAP子网,实验数据表明,该子网覆盖了上海社区网的大部分热门栏目页面。     

路径表达式的构造方法及路径测试

软件测试是软件设计中一个重要阶段,也是保证软件可靠性的重要手段。路径测试是软件测试中一种重要方法,而测试的关键是确定路径数目和设计测试用例。程序路径表达式是路径测试中路径的一种表示方法。本文讨论了利用程序图进行路径测试中的路径表达式的构造方法。     

A decision tree approach to graph and subgraph isomorphism detection

A new approach to the problem of graph and subgraph isomorphism detection from an input graph to a database of model graphs is proposed in this paper. It is based on a preprocessing step in which the model graphs are used to create a decision tree. At run time, subgraph isomorphisms are detected by means of decision tree traversal. If we neglect the time needed for preprocessing, the computational complexity of the new graph algorithm is only polynomial in the number of input graph vertices. In particular, it is independent of the number of model graphs and the number of edges in any of the graphs. However, the decision tree is of exponential size. Several pruning techniques which aim at reducing the size of the decision tree are presented. A computational complexity analysis of the new method is given and its behavior is studied in a number of practical experiments with randomly generated graphs.     

Isomorphism for Graphs of Bounded Distance Width

In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth. GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable' polynomial time algorithms can be established. We introduce some new and natural graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve GRAPH ISOMORPHISM in O(n ² ) time for graphs with bounded rooted path distance width, and in O(n ³ ) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(n ^k+1 ) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters. Received February 18, 1997; revised February 23, 1998.     

超立方网络上的平行路径

超立方是分布存储系中最常用的结构。在以往的工作中,人们已经提出了不少容错寻径算法,然而,还没有考虑Ｈｎ中│Ｆ│≥２ｎ－２的情形,在一个含有故障结点集Ｆ的ｎ维超立方网络Ｈｎ中,│Ｆ│≤４ｎ－２４,（ｓ０,ｄ０）,（ｓ１,ｄ１）是其中任意两对非故障结点,结果,（１）对↓Ａｖ∈Ｖ（Ｈｎ）,有│Ａ（ｖ,Ｈｎ－Ｆ）│≥６．（２）沿着某一维ｋ（０≤ｋ≤ｎ－１）,可将Ｈｎ分割成两部分：（ｄ０∈）Ｈｎ－１,０和（     

The Euler Characteristics of Discrete Objects and Discrete Quasi-Objects

Assuming planar 4-connectivity and spatial 6-connectivity, we first introduce the curvature indices of the boundary of a discrete object, and, using these indices of points, we define the vertex angles of discrete surfaces as an extension of the chain codes of digital curves. Second, we prove the relation between the number of point indices and the numbers of holes, genus, and cavities of an object. This is the angular Euler characteristic of a discrete object. Third, we define quasi-objects as the connected simplexes. Geometric relations between discrete quasi-objects and discrete objects permit us to define the Euler characteristic for the planar 8-connected, and the spatial 18- and 26-connected objects using these for the planar 4-connected and the spatial 6-connected objects. Our results show that the planar 4-connectivity and the spatial 6-connectivity define the Euler characteristics of point sets in a discrete space. Finally, we develop an algorithm for the computation of these characteristics of discrete objects.     

基于知识图谱与关键词注意机制的中文医疗问答匹配方法

针对当前中文医疗领域高质量问答数据缺乏的问题,提出基于知识图谱与关键词注意机制的中文医疗问答匹配方法.首先,引入医学知识图谱,得到知识增强的句子特征.然后,加入关键词注意力机制,强调问题和答案句子之间的相互影响.在2个公开的中文医疗问答数据集cMedQA与webMedQA上的实验表明,当样本数据量较小时,文中方法的优势明显.消融实验也验证每个新增模块对文中方法的性能均有一定程度的提升.