三维带符号的欧氏距离变换及其应用

距离变换是图像处理中历史悠久的研究课题．该文将二维带符号的欧氏距离变换推广到三维，对其进行了优化，分析了它的计算复杂度，并应用于解决计算机图形学中的两个重要问题：第一，将图形对象的三角网格表示转换为它的距离场表示．即首先将三角网格模型离散为体素表示，利用三维带符号的距离变换，将求空间一点到图形对象的最短距离的全局搜索过程，转化为求这一点到离它最近的特征体素所包含的图形对象部分的局部搜索过程；第二，利用类似的思想，求两张空间曲面之间的最短距离．     

Allocating modules to processors in a distributed system

The author studies the complexity of the problem of allocating modules to processes in a distributed system to minimize total communication and execution costs. He shows that unless P=NP, there can be no polynomial-time ϵ-approximate algorithm for the problem, nor can there exist a local search algorithm that requires polynomial time per iteration and yields an optimum assignment. Both results hold even if the communication graph is planar and bipartite. On the positive side, it is shown that if the communication graph is a partial k-tree or an almost-tree with parameter k, the module allocation problem can be solved in polynomial time     

The recursive algorithm for the optimal static output feedbackcontrol problem of linear singularity perturbed systems

A recursive algorithm is developed for solving the algebraic equations comprising the solution of the optimal static output feedback control problem of singularly perturbed linear systems. The algorithm is very efficient from the numerical point of view, since only low-order systems are involved in algebraic calculations and the required solution can be easily obtained up to an arbitrary order of accuracy, that is O(ϵ^k) where ϵ is a small perturbation parameter. The real-world example demonstrates the failure of O(ϵ) theory used so far in the study of this problem and the necessity for the existence of O(ϵ^k) theory     

一类工作调度问题的回溯解法

回溯法是解决组合搜索问题的重要方法,该方法的搜索通过一个多阶段的确定过程来实现,在每一阶段都需要从一些选择中选择一个分支,一旦发现前面的选择不可能获得一个解,则算法进行回溯,即重新回到刚搜索过的选择点,并选择该结点另一个没有被试过的分支,如果该点处所有的分支都已试过,则算法回溯到该结点之前被选择的点.首先对一类分配调度问题进行了分析,然后提出一种基于回溯法的解决方案,并给出了算法的具体实现过程,最后对所提出算法的复杂度进行了分析.实验结果验证了方法的有效性.     

Superfaces: polygonal mesh simplification with bounded error

The algorithm presented simplifies polyhedral meshes within prespecified tolerances based on a bounded approximation criterion. The vertices in the simplified mesh are a proper subset of the original vertices. The algorithm, called Superfaces, makes two major contributions to the research in this area: it uses a bounded approximation approach, which guarantees that a simplified mesh approximates the original mesh to within a prespecified tolerance (that is, every vertex v in the original mesh will lie within a user specified distance ϵ of the simplified mesh); its face merging procedure is efficient and greedy-that is, it does not backtrack or undo any merging once completed and thus, the algorithm is practical for simplifying very large meshes     

3D distance fields: a survey of techniques and applications

A distance field is a representation where, at each point within the field, we know the distance from that point to the closest point on any object within the domain. In addition to distance, other properties may be derived from the distance field, such as the direction to the surface, and when the distance field is signed, we may also determine if the point is internal or external to objects within the domain. The distance field has been found to be a useful construction within the areas of computer vision, physics, and computer graphics. This paper serves as an exposition of methods for the production of distance fields, and a review of alternative representations and applications of distance fields. In the course of this paper, we present various methods from all three of the above areas, and we answer pertinent questions such as How accurate are these methods compared to each other? How simple are they to implement?, and What is the complexity and runtime of such methods?     

Fast and versatile algorithm for nearest neighbor search based on a lower bound tree

In this paper, we present a fast and versatile algorithm which can rapidly perform a variety of nearest neighbor searches. Efficiency improvement is achieved by utilizing the distance lower bound to avoid the calculation of the distance itself if the lower bound is already larger than the global minimum distance. At the preprocessing stage, the proposed algorithm constructs a lower bound tree (LB-tree) by agglomeratively clustering all the sample points to be searched. Given a query point, the lower bound of its distance to each sample point can be calculated by using the internal node of the LB-tree. To reduce the amount of lower bounds actually calculated, the winner-update search strategy is used for traversing the tree. For further efficiency improvement, data transformation can be applied to the sample and the query points. In addition to finding the nearest neighbor, the proposed algorithm can also (i) provide the k-nearest neighbors progressively; (ii) find the nearest neighbors within a specified distance threshold; and (iii) identify neighbors whose distances to the query are sufficiently close to the minimum distance of the nearest neighbor. Our experiments have shown that the proposed algorithm can save substantial computation, particularly when the distance of the query point to its nearest neighbor is relatively small compared with its distance to most other samples (which is the case for many object recognition problems).     

运用改进的八叉树算法实现精确碰撞检测

提出一种精确碰撞检测算法,通过计算空间多面体之间距离实现碰撞检测功能.在计算2个多面体之间距离时,运用空间层次划分技术高效地寻找多面体中充分接近的三角面片,然后在这些三角面片中进行距离计算,以提高算法效率;同时运用改进的八叉树层次分割算法,与基本八叉树算法相比,减少了算法的空间复杂度.文中算法已经在超导Tokamak实验装置（EAST）虚拟装配仿真系统的碰撞检测模块中得到应用,通过实验比较,证明了该算法的可行性.     

仿射子空间最近点分类算法

为了取得更好的识别效果,受支持向量机的几何解释和最近点问题启发,提出了一种新的模式分类算法——仿射子空间最近点算法。该算法是将支持向量机最近点法的最近点搜索区域由两类训练集凸包推广到两类训练样本各自张成的仿射子空间,并以仿射子空间作为样本分布的粗略估计,通过仿射子空间中的最近点对来构造平分仿射子空间间隔的最优分类超平面。该算法在ORL人脸识别数据库上进行的比较实验中取得了较好的识别效果,从而证实了该方法的可行性和有效性。     

基于Silverlight网页游戏的寻径优化算法

为了解决A*路径搜索算法在Silverlight网页游戏中的搜索费时和路径曲折等问题,在结合光线跨越算法和引入父结点指针的二叉堆存储开启列表的A*算法的基础上,提出了一种基于Silverlight网页游戏的寻径优化算法。该算法在现有研究的基础上使用光线跨越算法减小A*算法搜索规模,同时将动态关键点技术与光线跨越算法结合来优化算法返回的路径。将该算法在游戏所使用的网格地图中进行实验,实验结果表明,该算法能够有效地根据系统设定的通行条件寻找出一条最优的实际可行的路径,同时缩短寻路的时间消耗和所寻的路径长度,提高游戏的可玩性。     

基于排除算法的快速三维人脸识别方法

提出了一种基于排除算法的快速三维人脸识别方法. 首先, 利用主成分分析(Principal component analysis, PCA)对自动切割的不同姿态人脸进行校正, 将所有人脸转换到统一的坐标系下; 然后提取人脸侧面轮廓线, 利用基于LTS-Hausdorff距离的轮廓线对齐方法对库集对象进行排除; 最后, 采用基于刚性区域的改进迭代最近点(Iterative closest point, ICP)算法对剩余的库集模型进行精确匹配, 给出最终识别结果. 在FRGC V2.0人脸数据库的实验结果表明, 该方法具有较好的实时性和鲁棒性.     

求极小碰集的蛛网算法

为降低空间复杂度和减少搜索时间,结合极小碰集的特点和生物学中蜘蛛捕食思想,提出了一种搜索极小碰集的蛛网算法。该方法考虑集合之间的相关性,并构造能在蛛网上寻路的访问蜘蛛用于寻找蛛网内集合的所有极小碰集。在该算法中,所提出的访问蜘蛛生成和搜索策略能够降低空间复杂度和减少搜索时间。将此算法与其他的极小碰集算法进行比较,实验结果表明,该算法在保证得到所有极小碰集的前提下,具有较低的空间复杂度和较高的时间效率。     

An efficient Earth Mover's Distance algorithm for robust histogram comparison

We propose EMD-L1: a fast and exact algorithm for computing the Earth Mover's Distance (EMD) between a pair of histograms. The efficiency of the new algorithm enables its application to problems that were previously prohibitive due to high time complexities. The proposed EMD-L1 significantly simplifies the original linear programming formulation of EMD. Exploiting the L1 metric structure, the number of unknown variables in EMD-L1 is reduced to O(N) from O(N2) of the original EMD for a histogram with N bins. In addition, the number of constraints is reduced by half and the objective function of the linear program is simplified. Formally, without any approximation, we prove that the EMD-L1 formulation is equivalent to the original EMD with a L1 ground distance. To perform the EMD-L1 computation, we propose an efficient tree-based algorithm, Tree-EMD. Tree-EMD exploits the fact that a basic feasible solution of the simplex algorithm-based solver forms a spanning tree when we interpret EMD-L1 as a network flow optimization problem. We empirically show that this new algorithm has an average time complexity of O(N2), which significantly improves the best reported supercubic complexity of the original EMD. The accuracy of the proposed methods is evaluated by experiments for two computation-intensive problems: shape recognition and interest point matching using multidimensional histogram-based local features. For shape recognition, EMD-L1 is applied to compare shape contexts on the widely tested MPEG7 shape data set, as well as an articulated shape data set. For interest point matching, SIFT, shape context and spin image are tested on both synthetic and real image pairs with large geometrical deformation, illumination change, and heavy intensity noise. The results demonstrate that our EMD-L1-based solutions outperform previously reported state-of-the-art features and distance measures in solving the two tasks.     

一种快速检测图像角点特征的线搜索式方法

传统的图像角点特征检测方法在速度和准确性两方面难以兼顾. 针对该问题, 提出了一种角点特征检测的线搜索式方法. 该方法作用于一个以当前像素为中心核的圆掩模, 在该掩模内搜索通过核的所有直线, 如果存在一条直线不穿过核附近给定邻域以外的其他同值收缩核(Univalue segment assimilating nucleus, USAN)区域, 则当前像素点为角点. 论文论证了使用有限数目搜索线的可行性与必要性. 采用由粗及细的搜索策略, 动态设计搜索线的数目与搜索线上的检测点数目, 以提高检测速度. 提出了一种基于最大同值距离的新型非极大值抑制进行角点的精确定位, 并结合多种新型伪响应抑制措施, 有效地提高了算法的准确度. 实验结果表明该方法在准确性方面优于MIC、SUSAN和Harris等算法, 而且速度快, 仅稍慢于MIC算法, 具有优良的综合性能.     

基于邻域曲率的低特征辨识度点云配准方法

在对特征辨识度低的点云进行配准的过程中,传统的基于局部特征提取和匹配的方法通常精度不高,而基于全局特征匹配的方法精度和效率也难以保证。针对这一问题,提出一种改进的局部特征配准方法。在初步配准阶段,设计了一种基于法向量投影协方差分析的关键点提取方法,结合快速特征直方图(FPFH)对关键点进行特征描述,定义多重匹配条件对特征点进行筛选,最后将对应点的最近距离之和作为优化目标进行粗匹配;在精配准阶段,采用以点到平面的最小距离作为迭代优化对象的改进迭代最近点(ICP)算法进行精确配准。实验结果表明,在配准特征辨识度低的点云时,相较于其他三种配准方法,该方法能保持高配准精度的同时降低配准时间。     

Parallel algorithms for relational coarsest partition problems

Relational Coarsest Partition Problems (RCPPs) play a vital role in verifying concurrent systems. It is known that RCPPs are P-complete and hence it may not be possible to design polylog time parallel algorithms for these problems. In this paper, we present two efficient parallel algorithms for RCPP in which its associated label transition system is assumed to have m transitions and n states. The first algorithm runs in O(n^1+ϵ) time using m/n^ϵ CREW PRAM processors, for any fixed ϵ<1. This algorithm is analogous to and optimal with respect to the sequential algorithm of P.C. Kanellakis and S.A. Smolka (1990). The second algorithm runs in O(n log n) time using m/n CREW PRAM processors. This algorithm is analogous to and nearly optimal with respect to the sequential algorithm of R. Paige and R.E. Tarjan (1987)     

基于优先级分组的防碰撞算法

针对在标签数量较多、运动较快的场合,常存在识别效率低且标签漏读率高的问题,提出一种先分组再处理的防碰撞算法——PAJS。该算法按照到达顺序对标签进行分组,以减小漏读率;根据标签识别过程中时隙状况自适应调整帧长度,提高算法的搜索效率;采用跳跃式动态搜索算法处理冲突时隙,从而减少搜索次数和系统传输量。Matlab仿真结果表明,该算法通信复杂度明显小于其他常用算法,吞吐率可达0.59~0.6。在待识别标签较多的场合,该算法优越性更加明显。     

An Improved Algorithm for Finding the Closest Pair of Points

As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to （3n lg n）/2, which is only half that of SH algorithm.     

用于AVS视频编码的三步快速子像素搜索算法

AVS是中国自主制定的音视频编码标准,在视频编码算法中采用子像素搜索方法,使搜索更精确、压缩效果更好,但算法复杂度较高。基于搜索点失真随着与全局最小点之间距离的增加而增大,以及运动矢量具有中心偏置的特性,该文提出一种三步快速子像素搜索算法。实验结果表明,该算法与标准算法相比,在保证视频质量基本不变的同时,复杂度降低了65%以上。     

求平面点集最近点对的一个改进算法

文中对Ｐｒｅｐａｒａｔａ和Ｓｈａｍｏｓ在１９８５年提出的求平面点集最近点对的一个分治算法进行了改进，使原来 归并时最多需计处３ｎ对点对的距离，改进的为最多只需计算２ｎ