基于区域正交化分割的平面点集凸包算法EI北大核心CSCD

为解决实际工程应用中具有超大规模的平面点集的凸包计算问题,提出了一种基于点集所在区域正交化分割的新算法.利用点集几何结构的部分极点对平面点集进行正交化分割,以获取不相干的点集子集簇,再对所有点集子集分别计算其凸包极点,最后合并极点得到凸包点集.在不同层级的正交化分割过程中,根据已知极点的信息,逐层舍去对于凸包极点生成没有贡献的无效点,进而提高算法运行效率.在与目前常用凸包算法的对比实验中,该算法处理超大规模的平面点集时稳定性高且速度更快.     

Bijective Digitized Rigid Motions on Subsets of the Plane

Rigid motions in \(\mathbb {R}^2\) are fundamental operations in 2D image processing. They satisfy many properties: in particular, they are isometric and therefore bijective. Digitized rigid motions, however, lose these two properties. To investigate the lack of injectivity or surjectivity and more generally their local behavior, we extend the framework initially proposed by Nouvel and Rémila to the case of digitized rigid motions. Yet, for practical applications, the relevant information is not global bijectivity, which is seldom achieved, but bijectivity of the motion restricted to a given finite subset of \(\mathbb {Z}^2\). We propose two algorithms testing that condition. Finally, because rotation angles are rarely given with infinite precision, we propose a third algorithm providing optimal angle intervals that preserve this restricted bijectivity.     

基于凸面单形体的Vague集向Fuzzy集转化模型

利用Vague集与凸面单形体同一平面内3个三角形的对应关系,给出一种Vague集及其向Fuzzy集转化的单形体几何表示方法,有效解决Vague集向Fuzzy集转化方法或模型中的几何解释问题。提出Vague集向Fuzzy集转化的单形体转化模型(S-TM),以及应满足的转化准则。与已有转化方法或模型相比,S-TM具有更直观的几何表示和更明确、更确定的几何解释,是一种更为有效的转化模型,并说明Vague集向Fuzzy集的转化具有模糊性和逐渐转化性。     

The Convex Hull of Rational Plane Curves

We present an algorithm that computes the convex hull of multiple rational curves in the plane. The problem is reformulated as one of finding the zero-sets of polynomial equations in one or two variables; using these zero-sets we characterize curve segments that belong to the boundary of the convex hull. We also present a preprocessing step that can eliminate many redundant curve segments.     

平面线段集三角剖分的算法

本文提出了计算平面线段集三角剖分的两种算法，第一个算法是利用平面扫描的思想，当扫描线达到事件点时，处理事件点，即将事件点与已被扫描的某些点连接，这样便将已扫描的区域三角剖分，当扫描线达到最左边的事件点时，处理该事件点，就完成了平面线段集的三角剖分，第二个算法基于逐层计算凸壳，并将凸壳改变为多边形，这样便便形成嵌套的多边形层，这些多边形覆盖线段集凸壳内的区域，然后三角剖分每个多边形，即完成平面线段集的三角剖分，两个算法的时间复杂性分别为O（nlogn),O(mnlogn)，其中n为线段集中线估的数目，m为凸壳的层数。     

Convex Drawings of 3-Connected Plane Graphs

We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings on a grid of size The parameter depends on the Schnyder wood used for the drawing. This parameter is in the range The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs. The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing of a random triangulation is close to For a random 3-connected plane graph, tests show that the expected size of the drawing is      

The Digital Topology of Sets of Convex Voxels

Classical digital geometry deals with sets of cubical voxels (or square pixels) that can share faces, edges, or vertices, but basic parts of digital geometry can be generalized to sets S of convex voxels (or pixels) that can have arbitrary intersections. In particular, it can be shown that if each voxel P of S has only finitely many neighbors (voxels of S that intersect P), and if any nonempty intersection of neighbors of P intersects P, then the neighborhood N(P) of every voxel P is simply connected and without cavities, and if the topology of N(P) does not change when P is deleted (i.e., P is a “simple” voxel), then deletion of P does not change the topology of S.     

Small Strictly Convex Quadrilateral Meshes of Point Sets

In this paper we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that 3\lfloorn/2\rfloor internal Steiner points are always sufficient for a convex quadrilateral mesh of n points in the plane. Furthermore, for any given n\geq 4, there are point sets for which \lceil(n–3)/2\rceil–1 Steiner points are necessary for a convex quadrilateral mesh.     

Small Strictly Convex Quadrilateral Meshes of Point Sets

In this paper we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that 3\lfloorn/2\rfloor internal Steiner points are always sufficient for a convex quadrilateral mesh of n points in the plane. Furthermore, for any given n\geq 4, there are point sets for which \lceil(n–3)/2\rceil–1 Steiner points are necessary for a convex quadrilateral mesh.     

基于识别的凸集投影人脸图像超分辨率重建

人脸图像的超分辨率重建在公安、视频监控等领域有重要应用价值．基于识别的思想,对人脸灰度图像进行统计分析,得到有关人脸灰度整体特征的先验知识,将其描述为属性集合,从而利用凸集投影算法进行超分辨率图像重建．实验结果表明,重建质量较为理想,与通常的超分辨率凸集投影重建方法相比,抑制噪声的能力有显著提高,重建质量改善明显,收敛速度加快,且易于计算和实现．     

Analysis of Critical Damage in the Communication Network. II. Guaranteed Functional Performance Estimates

Journal of Computer and Systems Sciences International - In the computational experiments on a model of a multiuser communication and control network, changes in the system’s performance...     

Guaranteed Convergence Rate Estimates for a Class of Iterative Procedures: Their Comparison

The main difficulty in parallelization and synchronization of computations for speeding up the convergence of iterative procedures is the optimal guaranteed convergence rate estimation. A theorem is formulated concerning the guaranteed convergence rate estimates for certain procedures, in which resources are primarily allotted to the computation of nonlinearity components. Its proof is based on the use of new estimates for the spectral radii of the products of matrix sequences of asynchronous component computations.     

加权凸集投影法在分布式目标定位中的应用

针对基于能量的分布式目标定位算法——加权凸集投影法(POCS)精度不高、稳定性差的不足,提出一种加权POCS算法。在已有圆的方差基础上,推导出直线的方差,并建立POCS迭代步长与圆和直线方差的关系式,实现加权的迭代。通过控制到不同圆和直线的步长,减少噪声对定位的影响。实验证明,提出的加权POCS算法比普通POCS算法具有更高的精度和稳定性。     

计算平面点集凸包的实时插入算法

讨论平面点集的凸包实时插入算法。算法基于Graham扫描算法,对3个点检测顺序的转向。本文证明,当S的N个点以流的形式进入系统,计算S的凸包所需的检测次数小于3N。     

A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane

Computing the convex hull of a set of points is a fundamental operation in many research fields, including geometric computing, computer graphics, computer vision, robotics, and so forth. This problem is particularly challenging when the number of points goes beyond some millions. In this article, we describe a very fast algorithm that copes with millions of points in a short period of time without using any kind of parallel computing. This has been made possible because the algorithm reduces to a sorting problem of the input point set, what dramatically minimizes the geometric computations (e.g., angles, distances, and so forth) that are typical in other algorithms. When compared with popular convex hull algorithms (namely, Graham’s scan, Andrew’s monotone chain, Jarvis’ gift wrapping, Chan’s, and Quickhull), our algorithm is capable of generating the convex hull of a point set in the plane much faster than those five algorithms without penalties in memory space.     

一种基于凸集投影(POCS)的数字图像超分辨率重建算法

该文研究了一种基于凸集投影(POCS)算法的超分辨率图像重建方法,分析了POCS方法恢复图像的理论算法,通过仿真对比了其与双线性插值方法恢复超分辨率图像的差异,仿真结果表明,该方法明显地提高了超分辨率图像的恢复质量。     

Uniform Estimates of Attracting Sets of Extended Lurie Systems Using LMIs

This research presents a systematic procedure to obtain estimates, via extended Lyapunov functions, of attracting sets of a class of nonlinear systems, as well as an estimate of their stability regions. The considered class of nonlinear systems, called in this note the extended Lurie system, consists of nonlinear systems like those of the Lurie problem where one of the nonlinear functions can violate the sector conditions of the Lurie problem around the origin. In case of nonautonomous systems the concept of absolute stability is extended and uniform estimates of the attracting set are obtained. Two classical nonlinear systems, the forced duffing equation and the Van der Pol system, are analyzed with the proposed procedure.     

基于凸集投影（POCS）的车牌图像超分辨率重建研究

针对车牌识别中所拍摄的图像序列存在分辨率较低的问题,提出了利用图像间的互补信息来重建一幅高分辨率图像的方法,以便于车牌图像的识别。通过迭代求解法和高斯金字塔模型,快速精确地估计得到配准参数,采用凸集投影（POCS）算法对图像序列进行了超分辨率重建。实验表明算法具有亚像素级的配准精度和较强的稳健性,重建图像取得了良好的视觉效果。     

A Linear-Time Algorithm for Symmetric Convex Drawings of Internally Triconnected Plane Graphs

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem.