Isosurface construction in any dimension using Convex Hulls

We present an algorithm for constructing isosurfaces in any dimension. The input to the algorithm is a set of scalar values in a d-dimensional regular grid of (topological) hypercubes. The output is a set of (d-1)-dimensional simplices forming a piecewise linear approximation to the isosurface. The algorithm constructs the isosurface piecewise within each hypercube in the grid using the convex hull of an appropriate set of points. We prove that our algorithm correctly produces a triangulation of a (d-1 )-manifold with boundary. In dimensions three and four, lookup tables with 2/sup 8/ and 2/sup 16/ entries, respectively, can be used to speed the algorithm's running time. In three dimensions, this gives the popular marching cubes algorithm. We discuss applications of four-dimensional isosurface construction to time varying isosurfaces, interval volumes, and morphing.     

多核架构下计算凸壳的并行算法

改进了周培德的Z3-2算法,提出一种在多核架构下计算平面点集凸壳的并行算法。用“颜氏距离”来数字化平面上点与有向线段的位置关系,减少了计算次数和时间。进一步将原算法中比较耗时的两个过程分别在O(1)的时间复杂度内进行迭代分解,即当原问题规模大于给定阂值时,将原问题分解为若干个独立的子问题,若所得子问题的规模仍大于给定阂值,则再对子问题进行分解;所有子问题被加入并行任务组进行并行求解以充分利用多核处理器的并行计算资源。给出了算法的正确性说明,实验结果也表明本算法稳定高效。     

Largest and Smallest Convex Hulls for Imprecise Points

Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(nlog n) to O(n ¹³), and prove NP-hardness for some other variants.     

一种改进的快速三维凸包生成算法及实现

本文阐述一种快速的三维凸包构造新算法,算法吸收了Quick Hull方法中每次选用凸包的极值点(Extremal-Point)来构造新凸包的思想,在此基础上改进为选用二次极值点的方法来构造新凸包,并结合"冲突图"(Conflict-Graph)来更新凸包外的点和当前凸包的拓扑结构关系,从而取得了快速排除凸包的内部点、缩小问题规模、实现高效构建凸包的效果。本文算法的时间复杂度为O(nlgr),通过实验证明本文算法与QuickHull算法相比平均执行消耗时间减少20%,因此本算法具有理论和实际应用价值。     

Experiments in the Parallel Computation of 3D Convex Hulls

Two parallel implementations of a 3D convex hull algorithm are reported. The paper considers a MIMD distributed memory architecture and the implementations are carried out on the Meiko Computing Surface using T800 transputers and the programming languages Occam and C. The first method uses a simple parallel geometric decomposition strategy and produces encouraging results. With the second approach a parallel generic Divide-and-Conquer kernel is incorporated. This is an example of the algorithmic skeleton approach to parallel programming and involves run-time, dynamic allocation of work to processors. The resulting performances for both methods are measured and compared.     

基于凸包的齿痕点快速定位的方法研究

本文提出一种基于凸包的齿痕点的快速定位方法.在详细讨论了如何将图形学中的经典凸包算法应用于数字化中医舌诊的齿痕定位中后,通过相关舌图做实验,证明了该方法在快速齿痕点特征提取中的可行性、有效性和准确性.     

图像目标外接多边形及凸壳的一种构造方法

对二值图像进行Hough变换后,在(ρ,θ)空间中选取了一组边界对应点,通过计算与这些边界对应点对应的图像空间中直线的交点,构造了图像目标的外接多边形;通过比较相距π/2 rad的投影区间长度是否相等,或区间长度的乘积是否为最小,得到了形状外接正方形和外接最小面积矩形;利用构造形状外接多边形的方法并通过增加边的数目,构造了形状的近似凸壳.实验和理论分析表明,文中算法具有好的抗噪性能和广泛的适用范围.     

用兴趣点凸包和SVM加权反馈实现图像检索

针对采用环状颜色直方图的图像检索方法存在的不足,提出一种基于兴趣点凸包的图像特征提取方法,通过对用小波变换检测出的必趣点递归求出它们的凸包,并将每个凸包上的兴趣点按一定的算法安插在相应的桶内,对每个桶求出颜色直方图,利用桶与桶之间的相似度定义两幅图像的相似度.这种特征提取方法可有效抑制兴趣点集合中出现游离兴趣点的情况,结合基于兴趣点的空间离散度和Gabor小波纹理等特征实现图像检索,可有效提高图像检索精度.最后,提出一种新的相关反馈方法,通过利用支持向量机分类结果设置权值来改进移动查询点相关反馈方法.实际图像数据库上的实验表明,引入这种反馈方法后可将图像检索的查准率提高20%左右,查全率提高10%左右.     

Multidimensional Data Visualization Based on the Minimum Distance Between Convex Hulls of Classes

The problem of data visualization in the analysis of two classes in a multidimensional feature space is considered. The two orthogonal axes by which the classes are maximally separated from each other are found in the mapping of classes as a result of linear transformation of coordinates. The proximity of the classes is estimated based on the minimum-distance criterion between their convex hulls. This criterion makes it possible to show cases of full class separability and random outliers. A support vector machine is used to obtain orthogonal vectors of the reduced space. This method ensures the obtaining of the weight vector that determines the minimum distance between the convex hulls of classes for linearly separable classes. Algorithms with reduction, contraction, and offset of convex hulls are used for intersecting classes. Experimental studies are devoted to the application of the considered visualization methods to biomedical data analysis.     

求解简单多边形和平面点集凸包的新算法

沿一定方向遍历凸多边形的边,其内部在边的同一侧。本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O（n log h）,其中,n为平面点集的点数,h为平面点集凸包的顶点数。相比相同复杂度的凸包算法,新算法简单、易于实现。又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效空间算法的优点。     

基于严凸函数的知识粒度与相对粒度

首次将严凸函数引入知识粒度研究中,提出基于严凸函数的知识粒度理论框架。根据该理论框架,给出一系列知识粒度度量函数,证明现有多种常见的知识粒度度量是该理论框架的特殊情形或变种。给出基于严凸函数的相对粒度定义,虽然对任意严凸函数导出的相对粒度不满足单调性,但对一些特殊严凸函数导出的相对粒度证明其单调性,并给出等号成立的条件。证明现有条件信息熵都是文中提出的严凸函数相对粒度的特殊情形,揭示它们的知识粒度本质。针对一致决策表,证明相对粒度与正区域不变等价,从而得到一致决策表代数约简的相对粒度判定方法。数值算例验证文中结论的正确性。     

Projective Visual Hulls

This article presents a novel method for computing the visual hull of a solid bounded by a smooth surface and observed by a finite set of cameras. The visual hull is the intersection of the visual cones formed by back-projecting the silhouettes found in the corresponding images. We characterize its surface as a generalized polyhedron whose faces are visual cone patches; edges are intersection curves between two viewing cones; and vertices are frontier points where the intersection of two cones is singular, or intersection points where triples of cones meet. We use the mathematical framework of oriented projective differential geometry to develop an image-based algorithm for computing the visual hull. This algorithm works in a weakly calibrated setting–-that is, it only requires projective camera matrices or, equivalently, fundamental matrices for each pair of cameras. The promise of the proposed algorithm is demonstrated with experiments on several challenging data sets and a comparison to another state-of-the-art method.     

On Minimum-Area Hulls

We study some minimum-area hull problems that generalize the notion of convex hull to star-shaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem: Given an n -vertex simple polygon P , find a minimum-area, star-shaped polygon P ^* containing P . This problem arises in lattice packings of translates of multiple, nonidentical shapes in material layout problems (e.g., in clothing manufacture), and has been recently posed by Daniels and Milenkovic. We consider two versions of the problem: the restricted version, in which the vertices of P ^* are constrained to be vertices of P , and the unrestricted version, in which the vertices of P ^* can be anywhere in the plane. We prove that the restricted problem falls in the class of ``3sum-hard' (sometimes called ``n ² -hard') problems, which are suspected to admit no solutions in o(n ² ) time. Further, we give an O(n ² ) time algorithm, improving the previous bound of O(n ⁵ ) . We also show that the unrestricted problem can be solved in O(n ² p(n)) time, where p(n) is the time needed to find the roots of two equations in two unknowns, each a polynomial of degree O(n) . We also consider the case in which P ^* is required to be monotone, with respect to an unspecified direction; we refer to this as the minimum-area monotone hull problem. We give a matching lower and upper bound of Θ(n log n) time for computing P ^* in the restricted version, and an upper bound of O(n q(n)) time in the unrestricted version, where q(n) is the time needed to find the roots of two polynomial equations in two unknowns with degrees 2 and O(n) . Received November 1996; revised March 1997.     

Progressive Hulls for Intersection Applications

Progressive meshes are an established tool for triangle mesh simplification. By suitably adapting the simplification process, progressive hulls can be generated which enclose the original mesh in gradually simpler, nested meshes. We couple progressive hulls with a selective refinement framework and use them in applications involving intersection queries on the mesh. We demonstrate that selectively refinable progressive hulls considerably speed up intersection queries by efficiently locating intersection points on the mesh. Concerning the progressive hull construction, we propose a new formula for assigning edge collapse priorities that significantly accelerates the simplification process, and enhance the existing algorithm with several conditions aimed at producing higher quality hulls. Using progressive hulls has the added advantage that they can be used instead of the enclosed object when a lower resolution of display can be tolerated, thus speeding up the rendering process. ACM CSS: I.3.3 Computer Graphics—Picture/Image Generation, I.3.5 Computer Graphics—Computational Geometry and Object Modeling, I.3.7 Computer Graphics—Three‐Dimensional Graphics and Realism     

Carved Visual Hulls for Image-Based Modeling

This article presents a novel method for acquiring high-quality solid models of complex 3D shapes from multiple calibrated photographs. After the purely geometric constraints associated with the silhouettes found in each image have been used to construct a coarse surface approximation in the form of a visual hull, photoconsistency constraints are enforced in three consecutive steps: (1) the rims where the surface grazes the visual hull are first identified through dynamic programming; (2) with the rims now fixed, the visual hull is carved using graph cuts to globally optimize the photoconsistency of the surface and recover its main features; (3) an iterative (local) refinement step is finally used to recover fine surface details. The proposed approach has been implemented, and experiments with seven real data sets are presented, along with qualitative and quantitative comparisons with several state-of-the-art image-based-modeling algorithms.     

自由拍摄视点下的可见外壳生成算法

给出了一种使用手持相机拍摄的多幅图像构造可见外壳的方法,该方法无需对相机运动方式作任何限定,而是利用多幅图像上的对应特征点求出每一幅图像的拍摄方位,因而可以非常灵活地获取某些较大规模的室外场景的几何模型．实验结果表明,利用该方法生成的可见外壳模型准确真实,能够满足虚拟现实等应用中的要求．     

基于退化多边形求交的多面体虚拟壳模型重构

三维模型的重建和表示是计算机图形和计算机视觉中一个重要的领域,其广泛应用于自动识别,工业自动化设计以及虚拟场景的重建。文中实现一个从照片序列重建三维物体多面体模型的系统,使用由轮廓恢复形体(SFS),通过经由轮廓光锥相交得到包围物体的虚拟壳。在系统中采用的共极线几何和增量运算把所有的三维的相交计算投射到二维平面的退化多边形求交来降低相交计算的复杂度。与传统多面体虚拟壳重构相比,算法有以下几点改进:在图像平面以退化多边形组织投影锥体和物体轮廓的交集,把任意锥面与物体轮廓的交集归一到一个退化多边形;基于退化多边形的二维平面上多边形快速相交算法。通过这些改进可以减少虚拟壳的生成时间并有助于实时绘制的实现。     

基于凸多边形的凸壳算法

确定平面点集的凸壳问题在计算机图形学、图像处理、CAD／CAM、模式识别等众多领域中有广泛的应用。本文根据凸多边形的性质构建了一种新的基于凸多边形的凸壳算法，该算法利用X、y坐标的极值将凸多边形分为几个段，应用凸壳顶点有序性，分段计算凸壳的顶点而得到凸壳。理论分析和实验结果表明，该算法运行速度快效率高，具有较强的实用性。