Computing the medial surface of a 3-D boundary representation model

Medial surface, the skeletal abstraction of a solid shape, can be used in applications such as shell (solid) mesh generation, robot path planning, and feature recognition. Unfortunately, computing the medical surface is very difficult. Those few algorithms proposed invariably need to solve systems of non-linear polynomial equations, which requires complicated numerical techniques. Recently, an algorithm has been proposed by the authors that is applicable to a polyhedral model. It uses voxel-bisector intersection relationships to calculate the intersection points and, from these, constructs the boundaries of the medical surface patches. Unfortunately, it does not handle the degenerate cases. This paper extends the scope of the voxel-bisector intersection algorithm by proposing a supplementary algorithm to detect the existence of the degenerate intersection curve in a specified region (voxel). An enhancement to the voxel-bisector intersection algorithm by using the Voronoi territory, which needs no polynomial root-finding scheme, is also proposed.     

An efficient algorithm for finding the CSG representation of a simple polygon

Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary.We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.The first author would like to acknowledge the support of the National Science Foundation under Grants CCR87-00917 and CCR90-02352. The fourth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the first author was visiting the DEC Systems Research Center.     

An optimal algorithm for the boundary of a cell in a union of rays

In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal Θ(n logn) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.     

An optimal algorithm for the boundary of a cell in a union of rays

In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal (n logn) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.This work was partly supported by CEE ESPRIT Project P-940, by the Ecole Normale Supérieure, Paris, and by NSF Grant ECS-84-10902.This work was done in part while this author was visiting the Ecole Normale Supérieure, Paris, France.     

CAD模型面的拓扑缺陷检测算法的设计

CAD模型在并行工程和协同设计环境下,在数据转换过程中可能会产生多种数据缺陷.针对这一问题,依据CAD数据质量标准,结合CAD模型面的拓扑结构的特点,对容易引发转换错误的反向的法向、边缘方位不一致、微小面数据缺陷进行了分类和描述.对前两类缺陷采用基于向量内积及夹角来构造检测算法,对微小面设计了基于二分扫描线的检测算法.利用VC++和UG/OpenAPI开发了面的拓扑缺陷检测系统,并通过3个代表性的实例验证算法的有效性.     

面向对象的专家知识模型

文中用面向对象方法来分析、设计基于规则的专家系统,提出一种新的采用分层递阶结构的专家知识模型,并从结构和功能角度进行详细阐述。     

An efficient algorithm for computing moments on a block representation of a grey-scale image

Computing lower order moments is important in image processing. Suppose the input grey image with size N×N has been compressed into the block representation where the number of blocks is K, commonly K<N² due to the compression effect. This correspondence presents an efficient algorithm for computing lower order moments on the block representation directly. Our proposed algorithm takes O(K) time which is proportional to the number of blocks. Experimental results reveal the computational advantage of our proposed algorithm. In addition, the results of this paper can be viewed as a generalization of the previous result by Spiliotis and Mertzios for computing lower order moments from the binary image domain to the grey image domain.     

An algorithm for solving multi-point boundary value problems

We describe a method for computing solutions of multi-point boundary value problems, where the polychotomic structure of the underlying solution space is specifically exploited. After the system is integrated in a multiple shooting way, the resulting linear system is solved by a special decoupling algorithm that takes into account the fact that the dichotomy on each interval is potentially different (in contrast to the two point case). A number of examples sustains the theory.     

An iterative learning algorithm for boundary control of a stretched moving string

In this paper, iterative learning control technique is applied for the first time to a class of flexible systems. Specifically, learning control of a material transport system is considered. The system consists of a stretched string and a transporter. The motion of transporter is subject to such external disturbances as imperfect wheels and can cause string vibrations. The control objective is to damp out any string oscillation during transportation using iterative control applied at the boundaries. The control is designed using both discrete and continuous time Lyapunov functions. The proposed result is new and significant as it demonstrates that iterative learning control methodology is an effective technique for controlling distributed parameter systems.     

An automatic algorithm for approximating boundary of bitmap characters

In this paper, an automatic and efficient algorithm for outline capture of character images, stored as bitmap, is presented. This method is well suited for characters of non-Roman languages like Arabic, Japanese, Urdu, Persian, etc. Contemporary word processing systems store shapes of the characters in terms of their outlines, and outlines are expressed as cubic Bezier curves. The process of capturing outlines includes steps: detection of boundary, finding Corner Points and Break Points and fitting the curve. The work done in this paper, fully automate the above process and produces optimal results.     

An improved algorithm for gray image representation using non-symmetry and anti-packing model with triangles and rectangles

Although the triangle non-symmetry and anti-packing model (TNAM) representation for gray images is an effective image representation method, there is still much space left for optimization. In this paper, inspired by the optimization idea of the packing problem, we proposed an improved algorithm for gray image representation using the non-symmetry and anti-packing model with triangles and rectangles (NAMTR). By comparing the representation algorithm of the NAMTR with those of the TNAM and the popular linear quadtree, theoretical and experimental results presented in this paper show that the former can greatly reduce the number of sub-patterns or nodes and simultaneously save the data storage much more effectively than the latter, and therefore it is a better method to represent gray images. Representation method of the NAMTR, as envisaged in this paper, shows a very strong promise, and it is valuable for further theoretical research and potential business foreground, such as reducing storage space, increasing transmission speed and improving pattern match efficiency.     

An auction-based market equilibrium algorithm for a production model

We present an auction-based algorithm for computing market equilibrium prices in a production model, in which producers have a single linear production constraint, and consumers have linear utility functions. We provide algorithms for both the Fisher and Arrow–Debreu versions of the problem.     

An efficient DIPIE algorithm for CAD of electrostatically actuated MEMS devices

Pull-in parameters are important properties of electrostatic actuators. Efficient and accurate analysis tools that can capture these parameters for different design geometries, are therefore essential. Current simulation tools approach the pull-in state by iteratively adjusting the voltage applied across the actuator electrodes. The convergence rate of this scheme gradually deteriorates as the pull-in state is approached. Moreover, the convergence is inconsistent and requires many mesh and accuracy refinements to assure reliable predictions. As a result, the design procedure of electrostatically actuated MEMS devices can be time-consuming. In this paper a novel Displacement Iteration Pull-In Extraction (DIPIE) scheme is presented. The DIPIE scheme is shown to converge consistently and far more rapidly than the Voltage Iterations (VI) scheme (>100 times faster!). The DIPIE scheme requires separate mechanical and electrostatic field solvers. Therefore, it can be easily implemented in existing MOEMS CAD packages. Moreover, using the DIPIE scheme, the pull-in parameters extraction can be performed in a fully automated mode, and no user input for search bounds is required.     

An Object-Logic model for the representation and processing of design standards

There are two distinct categories of knowledge in a design standard: (1) knowledge of the organization of design objects and (2) knowledge of the methods used in reasoning about the design objects. The object-oriented paradigm lends itself naturally to representing the organizational aspect of the design standard. The logic programming paradigm, on the other hand, is well suited to implementing the reasoning mechanisms for design and conformance checking. The object-oriented and logic programming paradigms are combined to provide a unified Object-Logic model for the representation of design codes and the processing of design standards. By storing the design provisions in a knowledge base, the model is capable of performing conformance checking and component design. To evaluate the feasibility and practicality of this model, a prototype system, HyperLRFD++, has been implemented for parts of the American Institute of Steel Construction (AISC) Load and Resistance Factor Design (LRFD) specification and tested on sample problems.     

An investigation of the K-tree search algorithm for efficient case representation and retrieval

This paper presents a new method of retrieving cases from a case-base on the K-tree search algorithm. Building an automated CBR system relies on representing knowledge in an appropriate form and having efficient case retrieval methods. Using the Intelligent Business Process Reengineering System (IBPRS) architecture as a base, we discuss a model-based case representation approach to solve the knowledge elicitation bottleneck problems. In addition to presenting the model-based case representation method, we introduce a K-tree search method to transform the case base into a tree structure, and discuss how it can be applied to the case retrieval process in IBPRS. The basic idea of the algorithm is to use various attribute values defined in the case label as general information for the case matching and retrieval.     

一种障碍物模型检测算法

针对观测场景结构复杂、建模困难的问题,提出了一种基于运动目标跟踪的场景障碍物模型检测方法.结合对目标的检测与跟踪过程,利用空间投影关系确定场景中障碍物的位置,并将其映射到场景模型上,即可得到场景观测模型.该方法只需要对目标运动进行简单地跟踪和统计,不需要进行三维结构恢复以及图像拼接处理,能够有效解决场景的在线自适应建模问题.     

一种精度可控的CAD网格模型及轻量化算法的研究

针对现有三维CAD系统中,CAD网格模型显示精度固定,难以动态调整以及细分后网格数量过多等瓶颈问题,在原始模型基础上,结合CAD模型中边、面等几何与拓扑信息,提出了一种精度可控的三维CAD网格模型.根据该模型的结构特点,采用曲面内部插值与边界曲线插值相结合的轻量化分类细分算法来实现模型精度调整,并有效控制细分后的网格数量,可满足三维CAD系统对模型精度可控、减少网格数量的需要.     

An EM algorithm for the block mixture model

Although many clustering procedures aim to construct an optimal partition of objects or, sometimes, of variables, there are other methods, called block clustering methods, which consider simultaneously the two sets and organize the data into homogeneous blocks. Recently, we have proposed a new mixture model called block mixture model which takes into account this situation. This model allows one to embed simultaneous clustering of objects and variables in a mixture approach. We have studied this probabilistic model under the classification likelihood approach and developed a new algorithm for simultaneous partitioning based on the classification EM algorithm. In this paper, we consider the block clustering problem under the maximum likelihood approach and the goal of our contribution is to estimate the parameters of this model. Unfortunately, the application of the EM algorithm for the block mixture model cannot be made directly; difficulties arise due to the dependence structure in the model and approximations are required. Using a variational approximation, we propose a generalized EM algorithm to estimate the parameters of the block mixture model and, to illustrate our approach, we study the case of binary data by using a Bernoulli block mixture.