区域表示：线性四元树转换成边界链码

本文提出一种算法实现单连通区域的线性四元树表示转换成区域边界的4-方向链码描述。首先给出测定水平、垂直和对角方向邻接对的算法。利用这些算法的执行结果,可以定义一个边界四分形的边邻接方向矩阵。采用一组规则驱动该矩降,能够使转换过程用代数方法实现。     

一个基于线性四元树的连通标记算法

图象的四元树表示提供了有效地节省图象存储空间及快速地实施图象处理的方法,而利用四元树实现图象的连通标记则是图象处理、图象分析及计算机图形学中最基本的操作之一。文献〔1〕和〔2〕分别给出了基于指针四元树和线性四元树的图象连通标记算法。本文提出了一个新的基于线性四元树(Linear Quadtree,简称 LQT)的连通标记算法 CCL(T,N)(Connected Component Labeling),其算法平均时间复杂度与前两个算法相同,均为 O(N.logN),但其实用效率及通用性均优于前两者。     

一个基于四元树的图象平移算法

近年来,图象的四元树表示及在四元树上执行图象操作运算已有许多研究,其中图象平移是受到广泛注意的论题之一.但是,至今为止的主要研究工作均需要“排序”或“二分查找”技术实施图象平移操作,因而算法的时间复杂度过高,运行效率较低.本文给出了一个基于四元树的图象平移算法,突破了已有的传统研究方法,采用“活动边(active edge)”数据结构,在图象平移操作时保持“活动块(active block)”的信息,使算法既不需要“排序”也不需要“搜索”,因而大大降低了时间复杂度.大量的对比实验也表明了该算法的可行性和有效性.     

区域表示：二元数组转换成线性四元树

本文提出一种方法实现二值图象的二元数组表示转换成线性四元树描述。它包括两个算法:(1)二元数组转换成0-四分形集合,和(2)平移-合并0-四分形。对于二元数组,算法(1)需要O(2~(2n))时间。算法(2)以0-四分形数目的线性时间运行。     

基于四元数小波变换HMT模型的图像去噪

实小波变换域中的图像去噪会产生伪Gibbs现象,为此,提出一种基于四元数小波变换的隐马尔可夫树模型(Q-HMT),并应用于图像去噪。模型结合四元数小波变换理论与HMT模型,体现小波系数层间的相关性,捕获小波系数邻域的统计特征。实验结果表明,该模型的图像去噪效果在峰值信噪比以及视觉效果上均优于经典的去噪方法。     

线性四元树表示二值图像的围线追踪和Euler数的计算

本文将基于边过程的围线追踪算法推广应用于四元树表示的二值图像，给出了一个对线性四元树表示二值图像实现围线追踪的算法，算法利用输入的四分形编码确定四分形左上及右下角处象互的位置坐标，由此确定图像中的所有非零边过程，再进行基于边过程的围线追踪，算法求得围线的树结构，表达和图像的拓扑性质，利用围线的树结构给出了一个计算图像的Ｅｕｌｅｒ数的非常简便的方法。     

线性四分树表示的二值图像Euler数计算的邻接图搜索算法

利用无向邻接图描述线性四分树表示的二值图像四分形的邻接关系,在此基础上,提出了一种计算图象Euler数的有效算法,与已有的算法相比,该算法的显著特点是存储量小,便于计算机实现。     

用于区域表达的线性数字搜索树编码

本文提出一种用于区域表达的数据结构——数字搜索树(DST)及其线性化编码(LDST)。给出了在正方形区域图象最坏情况下的数据压缩公式,公式表明在图象分辨率较高时用LDST可使数据得到有效的压缩。最后,本文还给出了LDST与线性四叉树之间的转换算法及时间复杂度分析。     

广义线性八元树表示及物体的广义三维重建

提出物体的广义线性八元树表示法,推广线性八元树的构造方法完成物体的广义三维重建--广义线性八元树表示,从而为物体三维重建降低约束、增加灵活性.     

3D block-based medial axis transform and chessboard distance transform based on dominance

Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this paper. One of the significant properties is that CDT for 3D binary image V is equal to BB-MAT for image V' where it denotes the inverse image of V. In a parallel algorithm, a cost is defined as the product of the time complexity and the number of processors used. The main contribution of this work is to reduce the costs of 3D BB-MAT and 3D CDT problems proposed by Wang [65]. Based on the reverse-dominance technique which is redefined from dominance concept, we achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N³, our parallel algorithm can be run in O(logN) time using N³ processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. The presented results for the cost are reduced in comparison with those of Wang's. To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known. In parallel algorithms, the running time can be divided into computation time and communication time. The experimental results of the running, communication and computation times for the different problem sizes are implemented in an HP Superdome with SMP/CC-NUMA (symmetric multiprocessor/cache coherent non-uniform memory access) architecture. We conclude that the parallel computer (i.e., SMP/CC-NUMA architecture or cluster system) is more suitable for solving problems with a large amount of input size.     

一种改进的中轴骨架三维模型检索算法

针对三维模型检索算法性能较低的问题,提出了一种改进的中轴骨架三维模型检索算法。     

基于整数中轴骨架的3维模型检索算法

针对3维模型检索算法性能较低的问题,提出了一种基于整数中轴骨架的3维模型检索算法。在对3维模型进行姿态调整和各向同向性预处理后,提取模型的整数中轴骨架,并记录每个骨架点相应的几何信息,对提取的骨架按不同的空间区域划分,形成模型骨架二叉树。为了能够描述骨架二叉树的不同节点对模型整体相似性匹配的影响程度,为每个节点定义一个特征权值,其大小由该节点对应的骨架区域大小所决定。最后,采用由粗到细逐步淘汰的策略计算不同模型的相似度。对一个标准3维模型测试数据库的检索实验结果表明,由于将模型的拓扑结构和统计特征相结合,该算法可以得到较好的检索性能。     

动态骨架算法

骨架是表示物体形状的一种有效形式.基于距离变换的骨架求解算法得到的骨架尽管准确光滑,但必须仔细地检查其连续性;而当骨架的结构较为复杂时,这种连续性检查会变得非常困难.结合Thinning技术和Snake模型,提出了一个平面二值图的动态骨架算法.首先利用Thinning技术生成连续且拓扑保持的初始骨架,然后根据Snake模型的思想,将初始骨架引导到正确的位置上.动态骨架算法提取的骨架不仅保持了位置的准确和外形的光滑,同时也解决了骨架的连续性问题.     

Linear One-Sided Stability of MAT for Weakly Injective Domain

Medial axis transform (MAT) is very sensitive to noise, in the sense that, even if a shape is perturbed only slightly, the Hausdorff distance between the MATs of the original shape and the perturbed one may be large. But it turns out that MAT is stable, if we view this phenomenon with the one-sided Hausdorff distance, rather than with the two-sided Hausdorff distance. In this paper, we show that, if the original domain is weakly injective, which means that the MAT of the domain has no end point which is the center of an inscribed circle osculating the boundary at only one point, the one-sided Hausdorff distance of the original domain's MAT with respect to that of the perturbed one is bounded linearly with the Hausdorff distance of the perturbation. We also show by example that the linearity of this bound cannot be achieved for the domains which are not weakly injective. In particular, these results apply to the domains with sharp corners, which were excluded in the past. One consequence of these results is that we can clarify theoretically the notion of extracting the essential part of the MAT, which is the heart of the existing pruning methods.     

Medial Axes and Mean Curvature Motion II: Singularities

What happens to the medial axis of a curve that evolves through MCM (Mean Curvature Motion)? We explore some theoretical results regarding properties of both medial axes and curvature motions. Specifically, using singularity theory, we present all possible topological transitions of a symmetry set (of which the medial axis is a subset) whose originating curve undergoes MCM. All calculations are presented in a clear and organized fashion and are easily generalized for other front motions. A companion article deals with non-singular points of the medial axis through direct calculations.     

Voronoi diagrams of polygons: A framework for shape representation

This paper describes an efficient shape representation framework for planar shapes using Voronoi skeletons.This paper makes the following significant contributions. First a new algorithm for the construction of the Voronoi diagram of a polygon with holes is described. The main features of this algorithm are its robustness in handling the standard degenerate cases (colinearity of more than two points; co-circularity of more than three points), and its ease of implementation. It also features a robust numerical scheme to compute non-linear parabolic edges that avoids having to solve equations of degree greater than two. The algorithm has been fully implemented and tested in a variety of test inputs.Second, the Voronoi diagram of a polygon is used to derive accurate and robust skeletons for planar shapes. The shape representation scheme using Voronoi skeletons possesses the important properties of connectivity as well as Euclidean metrics. Redundant skeletal edges are deleted in a pruning step which guarantees that connectivity of the skeleton will be preserved. The resultant representation is stable with respect to being invariant to perturbations along the boundary of the shape. A number of examples of shapes with and without holes are presented to demonstrate the features of this approach.     

求成对线性规划问题的组合最优解的快速算法

本文研究求成对线性规划问题的组合最优解的算法，巧妙地将问题的求解转化成了求西凸多面体间的距离，并给出了求两凸多面体间距离的快速算法，以该算法为核心，一系列的成对线性规划问题的组合最优解的均能在Ｏ时间内求得。     

A Shape Metric for Blum Ribbons

A Blum ribbon is a figure whose boundary is the envelope of a family of circles the centers of which lie along a single unbranched curve called its medial axis. Define a Blum ribbon to be simple if its medial axis is the line segment joining points (0,0) and (1,0). Any Blum ribbon can be made simple by flexing the medial axis, rotating, then dilating, all of which are basic transformations in Blum's geometry of shape. The Lie group SL(2, R) acts on circles centered on the x-axis by linear fractional transformations. By means of this action it is possible to associate to any simple Blum ribbon a curve in SL(2, R). A distance between corresponding points lying on such curves is defined using the bi-invariant metric on SL(2, R). Resulting scale-invariant metrics on the set of figures defined as Blum ribbons are described and it is shown that these metrics can provide effective measures of shape difference.