Polygonal Representations of Digital Sets

In the context of discrete curve evolution the following problem is of relevance: decompose the boundary of a plane digital object into convex and concave parts. Such a decomposition is very useful for describing the form of an object, e.g. for shape databases. Although the problem is relatively trivial in ordinary plane geometry, in digital geometry its statement becomes a very difficult task due to the fact that in digital geometry there is no simple set-complement duality. The paper is based on results given by Hübler et al. The main new contribution of the paper is the generalization of the concepts introduced by these authors to nonconvex sets. The digital geometric low level segmentation of the boundary of a digital object can be used as a starting basis for further reduction of the boundary by means of discrete evolution.     

A semi-supervised approach to space carving

In this paper, we present a semi-supervised approach to space carving by casting the recovery of volumetric data from multiple views into an evidence combining setting. The method presented here is statistical in nature and employs, as a starting point, a manually obtained contour. By making use of this user-provided information, we obtain probabilistic silhouettes of all successive images. These silhouettes provide a prior distribution that is then used to compute the probability of a voxel being carved. This evidence combining setting allows us to make use of background pixel information. As a result, our method combines the advantages of shape-from-silhouette techniques and statistical space carving approaches. For the carving process, we propose a new voxelated space. The proposed space is a projective one that provides a colour mapping for the object voxels which is consistent in terms of pixel coverage with their projection onto the image planes for the imagery under consideration. We provide quantitative results and illustrate the utility of the method on real-world imagery.     

Steiner Minimal Trees with One Polygonal Obstacle

In this paper we study the Steiner minimal tree T problem for a point set Z with cardinality n and one polygonal obstacle ω in the Euclidean plane. We assume ω touches only one convex path in T that joins two terminals and that the number of extreme points of the obstacle is k . If all degree 2 vertices are omitted, then the topology of T is called the primitive topology of T . Given a full primitive topology along with ω convex, we prove that T can be determined in O(n ² +nlog ² k) time. Further, if ω is nonconvex, we then show that O(n ² +nklog k) time is required. Received April 16, 1996; revised August 18, 1997.     

Polygonal representation of digital planar curves through dominant point detection—a nonparametric algorithm

We describe a new algorithm that detects a set of feature points on the boundary of an 8-connected shape that constitute the vertices of a polygonal approximation of the shape itself. The set of feature points (nodes) is a ranked subset of the original shape points whose connected left and right arm extents cover the entire shape. Nodes are ranked based on their strength (in terms of their importance to other boundary points), length of support region, and distance from the centroid. The polygon obtained by linking the detected nodes approximates the contour in an intuitive way. The proposed algorithm does not require an input parameter and works well for shapes with features of multiple sizes.     

基于连接点的二维多角弧匹配

多角弧匹配问题的关键是，其既能反映多角弧的几何性质，又能反映多角弧拓扑结构的特征选取．在分析了多角弧几何形状的基础上，引入了连接点的概念，并用连接点集表示多角弧，这一表示在旋转和平移变换下是不变的。进一步取该连接点集作为匹配的特征集，给出了特征集之间匹配的算法．该算法是将连接点间的距离积分作为测量函数，使二维多角弧的匹配由连接点的匹配来决定．给出的模拟试验结果表明，该算法效果良好，并且对于数值污染具有健壮性。     

基于多边形拟合的细胞图像特征提取算法

细胞图像自动检验与识别是现在生物医学工程领域的一个热点问题.在细胞图像识别中传统应用目标的形状特征提取算法存在不足.为了提高图像提取精度,在分析边界直线拟合基础上提出了一种改进的细胞图像特征提取算法,建立基于平滑后边界拟合多边形的曲率向量、边长向量,分析定义了基于拟合多边形的拐点数、端点数,曲率均值、曲率方差、长轴、短轴、长短轴比、对称率、平行度等形状特征描述子.改进算法应用于蕞本形状与显微镜细胞图像中目标形状的特征提取,计算机仿真表明算法得到的形状描述子可以有效区分基本形状,并具有位移不变,并保证细胞图像提取的精度.     

基于SQLite内容雕刻的恢复技术

SQLite数据库被众多即时通信软件用于存储历史数据。在即时通信取证过程中,犯罪分子为阻碍司法部门的调查,往往隐藏、删除或覆盖重要的通信数据。目前的数据恢复方法效率较低,无法恢复被覆盖的数据。针对上述问题,提出了一种基于SQLite的内容雕刻算法,分析SQLite数据库文件的存储特性和数据删除机制,以空闲域为单位形成空闲域链表,以页结构为单位进行细粒度的内容雕刻,并根据数据被覆盖的位置对零散数据块进行有效拼接。实验结果表明,SQLite内容雕刻算法可有效在本地和移动终端恢复即时通信的历史数据,当数据库未受损时,恢复率可达到100%;而当删除域受到不同程度的覆盖时,恢复率仍然可达到50%左右,并具有较高的效率。     

以折线为母线的自相似分形图形的程序实现

自相似分形图形是分形图形的重要分支,以折线为母线的自相似分形图形是自相似分形图形的主要组成部分。该文对传统的根据具体母线形状编程画图的方法加以改进,给出了一个程序实现所有以折线为母线的自相似分形图形的作图方法并编写了实现该方法的源程序、源程序经编译连接形成可执行文件后,运行时只需在命令中给出母线数据,计算机便自动获取屏幕尺寸,确定图形大小和位置,然后将图形画出。     

Fast facial shape recovery from a single image with general, unknown lighting by using tensor representation

In this paper, we propose a fast 3-D facial shape recovery algorithm from a single image with general, unknown lighting. In order to derive the algorithm, we formulate a nonlinear least-square problem with two parameter vectors which are related to personal identity and light conditions. We then combine the spherical harmonics for the surface normals of a human face with tensor algebra and show that in a certain condition, the dimensionality of the least-square problem can be further reduced to one-tenth of the regular subspace-based model by using tensor decomposition (N-mode SVD), which greatly speeds up the computations. In order to enhance the shape recovery performance, we have incorporated prior information in updating the parameters. In the experiment, the proposed algorithm takes less than 0.4 s to reconstruct a face and shows a significant performance improvement over other reported schemes.     

Polygonal Shape Blending with Topological Evolutions

This paper presents a new general approach to blend 2D shapes with different topologies. All possible topological evolutions are classified into three types by attaching three different topological cells. This formalism is resulted from Morse theory on the behavior of the 3D surface around a non-degenerate critical point. Also we incorporate degenerate topological evolutions into our framework which produce more attractive morphing effects. The user controls the morph by specifying the types of topological evolutions as well as the feature correspondences between the source and target shapes. Some techniques are also provided to control the vertex path during the morphing process. The amount of user input required to produce a morph is directly proportional to the amount of control the user wishes to impose on the process. The user may allow the system to automatically generate the morph as well. Our approaches are totally geometric based and are easy and fast enough in fully interactive time. Many experimental results show the applicability and flexibility of our approaches.     

多边形近似曲线的基于排序选择的拆分合并算法

将遗传算法的排序选择策略引入到传统的拆分与合并算法,提出一种基于排序选择策略的拆分与合并算法（RSM）来求解平面数字曲线的多边形近似,解决了传统的拆分与合并算法对初始解的依赖问题．用2条通用的benchmark曲线对RSM算法进行测试,结果表明该算法的性能优于遗传算法和传统的拆分与合并算法．将RSM算法应用于湖泊卫星图像的多边形近似,取得了较好的近似效果．     

Benchmarking shape signatures against human perceptions of geometric similarity

Manual indexing of large databases of geometric information is both costly and difficult. Because of this, research into automated retrieval and indexing schemes has focused on the development of methods for characterising 3D shapes with a relatively small number of parameters (e.g. histograms) that allow ill-defined properties such as “geometric similarity” to be computed. However although many methods of generating these so called shape signatures have been proposed, little work on assessing how closely these measures match human perceptions of geometric similarity has been reported. This paper details the results of a trial that compared the part families identified by both human subjects and three published shape signatures.To do this a similarity matrix for the Drexel benchmark datasets was created by averaging the results of twelve manual inspections. Three different shape signatures (D2 shape distribution, spherical harmonics and surface portioning spectrum) were computed for each component in the dataset, and then used as input to a competitive neural network that sorted the objects into numbers of “similar” clusters. Comparison of human and machine generated clusters (i.e. families) of similar components allows the effectiveness of the signatures at duplicating human perceptions of shapes to be quantified.The work reported makes two contributions. Firstly the results of the human perception test suggest that the Drexel dataset contains objects whose perceived similarity levels ranged across the recorded spectrum (i.e. 0.1 to 0.9); Secondly the results obtained from benchmarking the three shape signatures against human perception demonstrate a low rate of false positives for all three signatures and a false negative rate that varied almost linearly with the amount of perceived similarity. In other words the shape signatures studied were reasonably effective at matching human perception in that they returned few wrong results and excluded parts in direct proportion to the level of similarity demanded by the user.     

Modifying the shape of B-spline surface with geometric constraints

The B-spline surface is one of the most commonly used parametric surface in computer aided geometric design and computer graphics. To develop more convenient techniques for designing and modifying B-spline surface is an important problem. A new method for the shape modification of B-spline surface with geometric constraints is presented in this paper. The deformation energy of the physically based B-spline surface is minimized based on finite element method, while geometric constraints including point, curve and boundary continuity constraints can be imposed to control the modified shape. By setting the external force zero, the surface is modified by the constraints solely. This lead to a simplified linear system to be solved and to eliminate the need of internal energy that could convert the iteration process of finite element function to a faster change for control points vector, such that the modified surface satisfies the given constraints. Practical examples are also given.     

Derivation of the functional relations between fractal dimension of and shape indices of urban form

The relationships between the size, scale, shape, and dimension of urban settlements are basic problems remained to be further resolved, and this paper provides an available perspective for understanding these problems. Based on the standard circle, the relations between the fractal dimension of urban boundary and the compactness ratios of urban shape were derived from a geometric measure relation in a simple way. The compactness ratios proved to be the exponential functions of the reciprocal of the boundary dimension. The results can be generalized and applied to the common indices of shape including circularity ratio, ellipticity index, and form ratio, which are defined by urban area, perimeter, or Feret’s diameter. The mathematical models are empirically verified by the remote sensing data of China’s 31 mega-cities in 1990 and 2000 and lend support to the assumption that urban boundaries are pre-fractals rather than real fractals. A conclusion can be drawn that there exist certain functional relations between the shape indices and the boundary dimension, and within certain range of scales, the fractal parameters can be indirectly estimated by the ratios of size measurements to reflect the features of urban shapes.     

Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbitrary topology

In this paper, a novel approach is proposed to reliably reconstruct the geometric shape of a physically existing object based on unorganized point cloud sampled from its boundary surface. The proposed approach is composed of two steps. In the first step, triangle mesh structure is reconstructed as a continuous manifold surface by imposing explicit relationship among the discrete data points. For efficient reconstruction, a growing procedure is employed to build the 2-manifold directly without intermediate 3D representation. Local and global topological operations with ensured completeness and soundness are defined to incrementally construct the 2-manifold with arbitrary topology. In addition, a novel criterion is proposed to control the growing process for ensured geometric integrity and automatic boundary detection with a non-metric threshold. The reconstructed manifold surface captures the object topology with the built-in combinatorial structure and approximates the object geometry to the first order. In the second step, new methods are proposed to efficiently obtain reliable curvature estimation for both the object surface and the reconstructed mesh surface. The combinatorial structure of the triangle mesh is then optimized by changing its local topology to minimize the curvature difference between the two surfaces. The optimized triangle mesh achieves second order approximation to the object geometry and can serve as a basis for many applications including virtual reality, computer vision, and reverse engineering.     

A geometric property of control systems with states in a Banach space

In this paper we are concerned with admissible trajectories x(·) of infinite-dimensional linear systems, defined on an interval [0, t₁] and such that x(0)−x(t₁) is small. We show that these trajectories satisfy certain geometric properties.     

Feedback stabilization of a linear control system in Hilbert space with ana priori bounded control

This paper derives a feedback controlf(t), ‖f(t)‖_E≦r,r>0, which forces the infinite-dimensional control systemdu/dt=Au+Bf, u(0)=u _o ≠H to have the asymptotic behavioru(t)→0 ast→∞ inH. HereA is the infinitesimal generator of aC _o semigroup of contractionse ^At on a real Hilbert spaceH andB is a bounded linear operator mapping a Hilbert space of controlsE intoH. An application to the boundary feedback control of a vibrating beam is provided in detail and an application to the stabilization of the NASA Spacecraft Control Laboratory is sketched. This research was sponsored in part by the Air Force Office of Scientific Research, Air Force Systems Command, USAF Contract/Grants AFOSR 81-0172 and AFOSR 87-0315.     

Consideration of illumination effects and optimization of window size for accurate calculation of depth map for 3D shape recovery

Obtaining an accurate and precise depth map is the ultimate goal for 3D shape recovery. For depth map estimation, one of the most vital parts is the initial selection of the focus measure and processing the images with the selected focus measure. Although, many focus measures have been proposed in the literature but not much attention has been paid to the factors affecting those focus measures as well as the manner the images are processed with those focus measures. In this paper, for accurate calculation of depth map, we consider the effects of illumination on the depth map as well as the selection of the window size for application of the focus measures. The resulting depth map can further be used in techniques and algorithms leading to recovery of three-dimensional structure of the object which is required in many high-level vision applications. It is shown that the illumination effects can directly result in incorrect estimation of depth map if proper window size is not selected during focus measure computation. Further, it is shown that the images need some kind of pre-processing to enhance the dark regions and shadows in the image. For this purpose, an adaptive enhancement algorithm is proposed for pre-processing. In this paper, we prove that without such pre-processing for image enhancement and without the use of proper window size for the estimation of depth maps, it is not possible to obtain the accurate depth map.     

Isogeometric topological shape optimization using dual evolution with boundary integral equation and level sets

An isogeometric topological shape optimization method is developed, using a dual evolution of NURBS curves and level sets; the NURBS curves feature the exact representation of geometry and the level sets help to detect and guide the topological variation of NURBS curves. The implicit geometry by the level sets is transformed into the parametric NURBS curves by minimizing the difference of velocity fields in both representations. A gradient-based optimization problem is formulated, based on the evolution of the NURBS curves. The control points of NURBS curves are taken as design variables. The necessary response and design sensitivity are computed by an isogeometric boundary integral equation method (BIEM) using the NURBS curves. The design sensitivity is obtained on fixed grids and utilized as the velocity to update the Hamilton–Jacobi equation for the level sets. To obtain the whole velocity field on the fixed grids, an interpolation and velocity extension scheme are employed. The developed method provides accurate response and enhanced sensitivity using isogeometric BIEM. Also, additional post-processing is not required to communicate with CAD systems since the optimal design is represented as NURBS curves. Numerical examples demonstrate the accuracy of design sensitivity on fixed grids and the feasibility of shape and topological optimization.     

Interpolating an unorganized 2D point cloud with a single closed shape

Given an unorganized two-dimensional point cloud, we address the problem of efficiently constructing a single aesthetically pleasing closed interpolating shape, without requiring dense or uniform spacing. Using Gestalt’s laws of proximity, closure and good continuity as guidance for visual aesthetics, we require that our constructed shape be a minimal perimeter, non-self intersecting manifold. We find that this yields visually pleasing results. Our algorithm is distinct from earlier shape reconstruction approaches, in that it exploits the overlap between the desired shape and a related minimal graph, the Euclidean Minimum Spanning Tree (EMST). Our algorithm segments the EMST to retain as much of it as required and then locally partitions and solves the problem efficiently. Comparison with some of the best currently known solutions shows that our algorithm yields better results.