基于加权割的图像分割

提出了一个新的图分割模型——加权割模型,设计了一个基于加权割的图像分割算法(Image segment-ation Algorithm Based on Weighted Cut,简记为ISAWC).加权割模型的特点是:(1)整合了图像的局部和整体分割信息;(2)在加权意义下最小化加权割能同时达到类间最大相异性和类内最大一致性.本文证明可通过求解一个特征向量问题来优化加权割.模拟点集和实际图像上的实验验证了ISAWC的有效性.     

共边排样件激光切割路径的规划

排样软件的应用使材料利用率得到了很大提高，然而后续切割软件若不能保证有效地切割零件、保证零件质量及提高生产率，则排样软件在材料利用率上获得的收益将丧失。基于图论学理论，建立了规则与非规则零件共边排样时激光切割路径规划的数学模型，给出了在充分考虑加工质量、加工效率、制造成本情况下的激光切割路径优化目标：打孔点最少以及切割中割嘴空行程最短。提出了满足激光切割工艺要求的三个切割路径优化算法：用于求解理想情况下共边切割路径优化问题的一个新的欧拉回路算法；基于奇度顶点完全图最小权最大匹配算法来求解一般情况下共边切割路径优化问题的算法；利用废料区域进一步减少打孔点的处理策略与求解算法。给出了各种算法的运行实例，验证了所提出的算法的有效性。     

适应于大幅面图像的快速匹配算法研究

基于特征的图像匹配算法具有更广的适用范围和更好的性能表现,但因为其算法更加复杂,使其很难满足实时性,尤其当图像尺寸变大后,这一缺点更加限制了此类算法在实际工程中的应用。针对这一问题,本文提出了一种新的用于大幅面图像的快速匹配算法。算法采用空域分割和频域压缩的方式对图像进行预处理。通过提取目标图中高频信息丰富的区域作为待匹配子图,减小用于匹配的目标图像尺寸;通过小波变换提取源图尺度空间的高尺度表示,压缩SIFT特征点在图像频域中的存在空间。算法采用由粗到细的匹配策略,粗定位待匹配子图在源图中的空间区域后,再次进行细匹配操作,最终实现大幅面图像间的快速匹配。仿真实验表明,新提出的算法极大地提高了大图像匹配的速度,在对部分算法模块进行硬件加速后,新提出的算法甚至可以满足实时性的要求。      

一种改进的图割目标分割算法

为了减少图像目标在分割过程中受到噪声、复杂背景等因素的影响,将图像的多特征信息引入到图割算法中,提出了一种结合图像的多特征信息图割目标分割方法。该方法先选取像素点的多种图像特征组成特征向量,并对已做好标记的目标和背景种子点的特征向量分别进行FCM聚类,然后分别计算各像素点与这两类种子点的各聚类中心的最短欧式距离,并据此信息完成对能量函数的构造,最终运用最大流/最小割的方法得到图像分割的结果。其与传统图割算法相比,分割结果有了明显改善。实验结果表明,该算法具有有效性。     

一种基于图割的全变差图像去噪算法

本文提出一种基于图割的全变差(TV)图像去噪算法.该算法将全变差去噪模型的能量函数最小化问题转化为图的最小割问题,然后采用图割技术(最大流/最小割算法)求得能量函数的全局最优解.并给出了去噪模型中,均衡系数的自适应设定方案.实验结果及分析表明,该算法能有效抑制以往最小化方法产生的阶梯效应,具有较优的复原效果.     

基于线段分割的图割立体匹配

提出了一种基于线段分割的图割立体匹配方法。首先,把图像的扫描线分割成不相重叠的、彩色-空间一致的线段基元。然后,在能量最小化框架下利用图割优化算法实现立体匹配,采用图割方法得到全局最优解,本算法中优化的节点不是传统的像素,而是分割得到的线段单元。图割方法是在拟合能量最优化的情况下给每个线段单元分配对应的视差来实现立体匹配的。多组测试数据上的实验结果说明了本方法的有效性。     

基于压缩传感和图割的多分辨率影像融合方法

针对像素级融合方法对高分辨率影像融合存在较大光谱细节保持问题,提出一种基于压缩传感和图割理论的多分辨率融合。在给定的全色和多光谱图像上用压缩传感的概念来获得融合图像的初始估计;用图割方法来最小化能量函数获得最终的融合图像。实验结果表明文中方法在相对整体维数综合误差(ERGAS),相关系数(CC),相对平均光谱误差(RASE)和光谱角映射(SAM)等方面有了很大提高,且融合后光谱细节特征保持较好。     

VLSI和PCB双层布线中的通孔最少化算法

本文提出了一个新的通孔最少化层分配的图模型．该模型克服了传统层分配算法对通孔度数和位置的限制，允许通孔自由地以任意度数和任何需要的位置出现．模型中还提出了通孔秩的概念，它比较能更精确地反映通孔的本质．在此基础上，本文将通孔最少化问题转化为图的最大割问题，并提出了一种启发式算法去求解图的最大割．算法已用Ｃ语言在ＳＵＮ工作站上实现．实验结果表明，算法十分有效且稳定．     

基于视差和帧差的图割优化运动目标分割算法

提出一种基于视差和帧差的图割优化运动目标分割算法,在运动目标分割过程中,利用能量函数优化方法得到较为准确的区域视差,同时在此基础上将视差和帧差特征采用图割算法的能量函数进行融合,以此提高前景目标分割的准确性。实验结果表明该方法当区域视差的优化受到灰度因素的影响时,利用图割结合视差和帧差特征能够有效地减少视差优化不够准确的区域被检测为前景目标的可能性,同时也能填补大多数帧差分割的空洞,增强了分割结果的稳定性。     

基于图割的单水平集迭代终止算法

针对C-V模型中变分水平集优化方法存在的最佳迭代次数难于确定,且容易陷入局部最优等不足,借鉴图割算法在较短时间内能得到全局最优的优势,提出一种基于图割的单水平集迭代终止算法.首先在目标区域设定一条初始轮廓线,采用无须重新初始化的C-V模型对轮廓线进行迭代,当轮廓线内部面积变化值小于预先给定的阈值时终止迭代,然后将此轮廓线作为图割算法的初始轮廓线进行图像分割.实验结果表明,该方法较原始C-V模型大大缩短了迭代时间,稳健性更高,具有较好的图像分割效果.     

On a new class of codes for identifying vertices in graphs

We investigate a new class of codes for the optimal covering of vertices in an undirected graph G such that any vertex in G can be uniquely identified by examining the vertices that cover it. We define a ball of radius t centered on a vertex υ to be the set of vertices in G that are at distance at most t from υ. The vertex υ is then said to cover itself and every other vertex in the ball with center υ. Our formal problem statement is as follows: given an undirected graph G and an integer t⩾1, find a (minimal) set C of vertices such that every vertex in G belongs to a unique set of balls of radius t centered at the vertices in C. The set of vertices thus obtained constitutes a code for vertex identification. We first develop topology-independent bounds on the size of C. We then develop methods for constructing C for several specific topologies such as binary cubes, nonbinary cubes, and trees. We also describe the identification of sets of vertices using covering codes that uniquely identify single vertices. We develop methods for constructing optimal topologies that yield identifying codes with a minimum number of codewords. Finally, we describe an application of the theory developed in this paper to fault diagnosis of multiprocessor systems     

有向图上k步可达查询处理

给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径。k步可达查询是一种基本的图操作并在过去十年间被广泛地研究。已有的k步可达查询算法仍存在许多弊端,例如不可达查询效率低,索引规模大和索引构建时间长等。本文针对上述问题提出了2种优化方法,分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率,后者减少了索引规模和索引构建时间。实验结果表明,本文提出的方法可以有效地处理k步可达查询,并支持大规模数据的处理。     

一种计算Ad hoc网络K-终端可靠性的线性时间算法

研究计算Ad hoe网络K-终端可靠性的线性时间算法,可以快速计算Ad hoe网络K-终端可靠性。为了计算Ad hoe网络分级结构尽终端可靠性,可以采用无向概率图表示Ad hoe网络的分级结构。每个簇头由已知失效率的结点表示,并且当且仅当两个簇相邻时,两个结点间的互连由边表示。这个概率图的链路完全可靠,并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算尽终端可靠性的一种线性时间算法。本算法可用来计算Ad hoe网络的K-终端可靠性。其时间复杂度为O（｜V｜＋｜E｜）。     

基于属性扩展图的聚类算法研究

提出一种新的图聚类算法,结合结点的结构及属性特性,使用统一的随机移动距离计算结点间的相似度,在邻接随机移动距离矩阵的基础上进行聚类.实验结果表明,基于属性扩展图的聚类算法在图拓扑结构的基础上,充分考虑了各个结点所拥有的属性特点,得到的聚类结果将更好的切合实际的应用.     

The Maximum Throughput of A Wireless Multi-Hop Path

In this paper, the maximum end-to-end throughput that can be achieved on a wireless multi-hop path is investigated analytically. The problem is modeled using the conflict graph, where each link in the multi-hop path is represented uniquely by a vertex in the conflict graph and two vertices are adjacent if and only if the associated links mutually interfere. Using the conflict graph and the linear programming formulations of the problem, we analyzed the maximum end-to-end throughput of a wireless multi-hop path a) in a simple scenario where nodes are optimally placed and each node can only interfere with the transmission of its adjacent nodes along the path, and b) in a more complicated scenario where nodes are randomly placed and each node can interfere with the transmission of any number of nearby nodes along the path in both a) an error free radio environment and b) an erroneous radio environment. The maximum end-to-end throughputs for each of the above four scenarios are obtained analytically. We show that the maximum achievable end-to-end throughput is determined by the throughput of its bottleneck clique, where a clique is a maximal set of mutually adjacent vertices in the associated conflict graph. Further our analysis suggests the optimum scheduling algorithm that can be used to achieve the maximum end-to-end throughput and that it is convenient to use the (maximal) independent sets as the basic blocks for the design of scheduling algorithms. The findings in this paper lay guidelines for the design of optimum scheduling algorithms. They can be used to design computationally efficient algorithms to determine the maximum throughput of a wireless multi-hop path and to design a scheduling algorithm to achieve that throughput.     

基于割点的路由缓存技术研究

由于Ad Hoc网络拓扑结构变化频繁,为了提高通信效率,减少路由发现的次数,在其中进行路由缓存就十分必要。通过对路由缓存的研究,基于图论中割点的概念对拓扑结构进行分析,提出了改进的路由缓存管理算法。该算法较大地提高了缓存路由的准确率和效率,更理想地适应了拓扑结构的变化。仿真结果表明,该算法改进了标准DSR路由协议的性能,保证了端到端平均时延降低的同时提高网络的吞吐量。     

基于决策树的一种改进算法

首先介绍了ID3算法的基本思想,然后讨论了决策树算法中的难点问题,针对ID3算法中所存在的不足,提出了一种利用优值法的思想来改进信息增益的算法,并且与ID3算法进行了实验对比。实验表明,这种方法从树的规模和分类精度都优于许多决策树算法,使决策效率明显提高。     

Decomposition Algorithms for Solving NP-hard Problems on a Quantum Annealer

NP-hard problems such as the maximum clique or minimum vertex cover problems, two of Karp’s 21 NP-hard problems, have several applications in computational chemistry, biochemistry and computer network security. Adiabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. However, this is often not possible due to certain limitations of the hardware connectivity structure of the annealer. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems aiming to identify an optimal set of vertices. Our generic algorithm allows us to recursively divide an instance until the generated subproblems can be embedded on the quantum annealer hardware and subsequently solved. The framework is applied to the maximum clique and minimum vertex cover problems, and we propose several pruning and reduction techniques to speed up the recursive decomposition. The performance of both algorithms is assessed in a detailed simulation study.

     

Grid Colorings in Steganography

A proper vertex coloring of a graph is called rainbow if, for each vertex v, all neighbors of v receive distinct colors. A k-regular graph G is called rainbow (or domatically full) if it admits a rainbow (k+1)-coloring. The d-dimensional grid graph G_d is the graph whose vertices are the points of Zopf^d and two vertices are adjacent if and only if their l₁-distance is 1. We use a simple construction to prove that G_d is rainbow for all d ges 1. We discuss an important application of this result in steganography     

Determination of All Minimal Cut-Sets between a Vertex Pair in an Undirected Graph

An efficient enumeration algorithm generates all minimal cut-sets separating a special vertex pair in an undirected graph. The algorithm is based on a blocking mechanism that guarantees that every minimal cut-set between the two specified vertices is generated exactly once. The algorithm is intended for computer implementation, and computational times are provided.