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.     

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

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

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

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

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.     

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

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

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.     

Design and Verification of Distributed Recovery Blocks with CSP

A case study on the application of Communicating Sequential Processes (CSP) to the design and verification of fault-tolerant real-time systems is presented. The distributed recovery block (DRB) scheme is a design technique for the uniform treatment of hardware and software faults in real-time systems. Through a simple fault-tolerant real-time system design using the DRB scheme, the case study illustrates a paradigm for specifying fault-tolerant software and demonstrates how the different behavioural aspects of a fault-tolerant real-time system design can be separately and systematically specified, formulated, and verified using an integrated set of formal techniques based on CSP.     

Bivariate C cubic spline space over a nonuniform type-2 triangulation and its subspaces with boundary conditions

In this paper, we discuss the algebraic structure of bivariate C¹ cubic spline spaces over nonuniform type-2 triangulation and its subspaces with boundary conditions. The dimensions of these spaces are determined and their local support bases are constructed.     

Heightfield and spatially varying BRDF Reconstruction for Materials with Interreflections

Photo-realistic reproduction of material appearance from images has widespread use in applications ranging from movies over advertising to virtual prototyping. A common approach to this task is to reconstruct the small scale geometry of the sample and to capture the reflectance properties using spatially varying BRDFs. For this, multi-view and photometric stereo reconstruction can be used, both of which are limited regarding the amount of either view or light directions and suffer from either low- or high-frequency artifacts, respectively. In this paper, we propose a new algorithm combining both techniques to recover heightfields and spatially varying BRDFs while at the same time overcoming the above mentioned drawbacks. Our main contribution is a novel objective function which allows for the reconstruction of a heightfield and high quality SVBRDF including view dependent effects. Thereby, our method also avoids both low and high frequency artifacts. Additionally, our algorithm takes inter-reflections into account allowing for the reconstruction of undisturbed representations of the underlying material. In our experiments, including synthetic and real-world data, we show that our approach is superior to state-of-the-art methods regarding reconstruction error as well as visual impression. Both the reconstructed geometry and the recovered SVBRDF are highly accurate, resulting in a faithful reproduction of the materials characteristic appearance, which is of paramount importance in the context of material rendering.