大口径精密光学元件表面疵病快速检测方法

为确保对大口径精密光学元件表面的疵病进行高效和准确检测,针对以往疵病检测系统不能处理单像素宽目标、提取疵病特征参数速度过慢等问题,提出了一种基于顶点链码与离散格林相结合的快速几何特征参数提取算法.算法把针对目标的曲面积分变为曲线积分,提取速度是以往方法的3倍左右;使多种几何特征参数的计算统一在该算法框架下,且能处理单像素宽的非闭合疵病;并在确保其泛化能力的基础上,运用机器学习的方式使疵病的分类识别率达到了90％以上.     

数字图像处理在顶点识别中的应用研究

图像检测中对2D图像的长度，面积测量，以及工件的某些指标的计算，常常会遇到顶点识别问题,锯齿型工件的锯齿顶点坐标的测量，是数字图像顶点识别中比例典型的例子，利用数字图像处理技术检测锯齿工件顶点，对图像进行了边缘检测，二值化，顶点识别处理，在顶点识别中还需剔除异常点，以减少识别错误率，描述了数字图像处理技术用于非接触精确测量的原理，对整个顶点识别过程做了详细的探讨，给出满意的识别结果。     

复杂几何模型动态视相关的简化

基于三角形网格边折叠的思想，提出了一种新的多边形简化算法以快速生成多层次细节的LOD模型，在折叠边的代价估计中，均衡考虑了多涟形边的长度和多边形表面曲率影响，折叠边的顶点位置从折叠边的顶点中选取，既有助于保留了初始模型的形状，又减少运算量，满足实时绘制的需求。在依据视点选择适当LOD模型时，采用了项点morphing技术光滑多边形模型，减少不同层次LOD模型转化时引起的图像‘跳跃’。在算法实现中，采用增强的多边形数据结构，并用一算例证明了算法的有效性。     

Linear-time algorithm for the matched-domination problem in cographs

Let G=(V, E) be a graph without isolated vertices. A matching in G is a set of independent edges in G. A perfect matching M in G is a matching such that every vertex of G is incident to an edge of M. A set S? V is a paired-dominating set of G if every vertex not in S is adjacent to a vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination problem is to find a paired-dominating set of G with minimum cardinality. This paper introduces a generalization of the paired-domination problem, namely, the matched-domination problem, in which some constrained vertices are in paired-dominating sets as far as they can. Further, possible applications are also presented. We then present a linear-time constructive algorithm to solve the matched-domination problem in cographs.? ^?A preliminary version of this paper has appeared in: Proceedings of the 4th IASTED International Conference on Computational Intelligence (CI’2009), Honolulu, Hawaii, USA, 2009, pp. 120–126.      

A learning approach to the bandwidth multicolouring problem

In this article, a generalisation of the vertex colouring problem known as bandwidth multicolouring problem (BMCP), in which a set of colours is assigned to each vertex such that the difference between the colours, assigned to each vertex and its neighbours, is by no means less than a predefined threshold, is considered. It is shown that the proposed method can be applied to solve the bandwidth colouring problem (BCP) as well. BMCP is known to be NP-hard in graph theory, and so a large number of approximation solutions, as well as exact algorithms, have been proposed to solve it. In this article, two learning automata-based approximation algorithms are proposed for estimating a near-optimal solution to the BMCP. We show, for the first proposed algorithm, that by choosing a proper learning rate, the algorithm finds the optimal solution with a probability close enough to unity. Moreover, we compute the worst-case time complexity of the first algorithm for finding a 1/(1–?) optimal solution to the given problem. The main advantage of this method is that a trade-off between the running time of algorithm and the colour set size (colouring optimality) can be made, by a proper choice of the learning rate also. Finally, it is shown that the running time of the proposed algorithm is independent of the graph size, and so it is a scalable algorithm for large graphs. The second proposed algorithm is compared with some well-known colouring algorithms and the results show the efficiency of the proposed algorithm in terms of the colour set size and running time of algorithm.     

通过三角形Strip衍生实现三维模型数据的渲染优化

GPU的顶点Cache命中率对三维渲染性能有着重大影响,而三维模型中的数据组织是GPU顶点Cache命中率的莺要因素.为此提出一种全新的模型Mesh优化方法.该方法从造成顶点Cache失效的基本情况出发,在模型Mesh中建立Seed Strip,并挑选与Seed Strip具有多个关联边的顶点进行Derived Strip衍生;通过反复地建立SeedStrip和衍生Derived Strip,得到一个优化的Mesh三角形序列,以有效地提高GPU的顶点Cache命中率,从而提高渲染效能.此外,该项工作还为进一步解决三维渲染中OverDraw问题预留了扩展的空间.     

Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph

This paper presents efficient algorithms for an interval graph. These are (1) an algorithm for counting the number of minimum vertex covers, and (2) an algorithm for counting the number of maximum minimal vertex covers.     

On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction

Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ₊ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v∈V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra’s algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s–t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor the minimum number of arcs which has to be removed to guarantee d(s,t)≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and/or node elimination. This research was supported in part by NSF grant IIS-0118635 and by DIMACS, the NSF Center for Discrete Mathematics & Theoretical Computer Science. Preprints DTR-2005-04 and DTR-2006-13 are available at and . Our co-author Leonid Khachiyan passed away with tragic suddenness on April 29th, 2005.     

基于特征点检测的最佳视点选择方法

针对三维模型视点选择问题,提出了基于特征点检测的最佳视点选择方法。算法首先根据三维网格模型的顶点邻接区域信息计算顶点的局部高度,即顶点的显著度大小;然后基于顶点的局部高度值大小,结合非极大值抑制算法进行三维模型表面特征点检测;最后针对视点球体上的每个候选视点分析该视点下可见特征点的几何分布信息,计算视点质量,从而筛选出最佳视点。实验结果验证了基于特征点检测的三维模型视点选择方法的合理性和优越性,所选择的最佳视点能够提供三维模型较多的几何结构和视觉特征信息。