Decomposition of two-dimensional shapes by graph-theoretic clustering

This paper describes a technique for transforming a twodimensional shape into a binary relation whose clusters represent the intuitively pleasing simple parts of the shape. The binary relation can be defined on the set of boundary points of the shape or on the set of line segments of a piecewise linear approximation to the boundary. The relation includes all pairs of vertices (or segments) such that the line segment joining the pair lies entirely interior to the boundary of the shape. The graph-theoretic clustering method first determines dense regions, which are local regions of high compactness, and then forms clusters by merging together those dense regions having high enough overlap. Using this procedure on handdrawn colon shapes copied from an X-ray and on handprinted characters, the parts determined by the clustering often correspond well to decompositions that a human might make.     

Convexity Rule for Shape Decomposition Based on Discrete Contour Evolution

We concentrate here on decomposition of 2D objects into meaningfulparts of visual form, orvisual parts. It is a simple observation that convex parts of objects determine visual parts. However, the problem is that many significant visual parts are not convex, since a visual part may have concavities. We solve this problem by identifying convex parts at different stages of a proposed contour evolution method in which significant visual parts will become convex object parts at higher stages of the evolution. We obtain a novel rule for decomposition of 2D objects into visual parts, called the hierarchical convexity rule, which states that visual parts are enclosed by maximal convex (with respect to the object) boundary arcs at different stages of the contour evolution. This rule determines not only parts of boundary curves but directly the visual parts of objects. Moreover, the stages of the evolution hierarchy induce a hierarchical structure of the visual parts. The more advanced the stage of contour evolution, the more significant is the shape contribution of the obtained visual parts.     

MINIMAL AND MAXIMAL SOLUTIONS OF A DECOMPOSITION PROBLEM OF FUZZY RELATIONS

In this work we continue the study already begun in our foregoing paper, dealing with the decomposition problem or a binary fuzzy relation defined in the Cartesian product of a finite space. We characterize the whole set of the solutions of the max-min fuzzy relation equation which formulates the decomposition problem.     

Topological solution of missing attribute values problem in incomplete information tables

In this paper, we present a new method of data decomposition to avoid the necessity of reasoning from data with missing attribute values. We define firstly a general binary relation on the original incomplete dataset. This binary relation generates data subsets without missing values. These data subsets are used to generate a topological base relation which decomposes datasets. We investigate a new approach to find the missing values in incomplete datasets. New pre-topological approximations are initiated and some of their properties are proved. Also, pre-topological measures are defined and studied. Finally, the reducts and the core of incomplete information system are determined.     

DECOMPOSITION PROBLEM OF FUZZY RELATIONS

The paper deals with a problem of decomposition of a binary fuzzy relation defined in the Cartesian product of a finite space. We propose an algorithm which produces the decomposition or indicates that the given relation is non-decomposable, within a finite sequence of steps.     

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.     

Efficient morphological shape representation by varying overlapping levels among representative disks

The morphological skeleton transform, the morphological shape decomposition, and the overlapped morphological shape decomposition are three basic morphological shape representation schemes. In this paper, we propose a new way of generalizing these basic representation algorithms to improve representational efficiency. In all three basic algorithms, a fixed overlapping policy is used to control the overlapping relationships among representative disks of different sizes. In our new algorithm, different overlapping policies are used to generate shape components that have different overlapping relationships among themselves. The overlapping policy is selected dynamically according to local shape features. Experiments show that compared to the three basic algorithms, our algorithm produces more efficient representations with lower numbers of representative points.     

快速模糊C均值聚类彩色图像分割方法

模糊C均值(FCM)聚类用于彩色图像分割具有简单直观、易于实现的特点，但存在聚类性能受中心点初始化影响且计算量大等问题，为此，提出了一种快速模糊聚类方法(FFCM)。这种方法利用分层减法聚类把图像数据分成一定数量的色彩相近的子集，一方面，子集中心用于初始化聚类中心点；另一方面，利用子集中心点和分布密度进行模糊聚类，由于聚类样本数量显著减少以及分层减法聚类计算量小，故可以大幅提高模糊C均值算法的计算速度，进而可以利用聚类有效性分析指标快速确定聚类数目。实验表明，这种方法不需事先确定聚类数目并且在优化聚类性能不变的前提下，可以使模糊聚类的速度得到明显提高，实现彩色图像的快速分割。     

The perimeter of a fuzzy set

In pattern recognition one often wants to measure the perimeters of regions in images. This is straightforward if the region is crisply defined, but if it is fuzzy, it is not obvious how its perimeter can be measured. This paper proposes a definition of perimeter for fuzzy subsets of the plane and shows that it reduces to the standard definition if the fuzzy subset is an ordinary subset. The isoperimetric inequality does not generalize to fuzzy subsets, but certain properties of the perimeters of convex sets do generalize to fuzzy perimeters of convex fuzzy subsets.     

A new point symmetry based fuzzy genetic clustering technique for automatic evolution of clusters

In this paper a fuzzy point symmetry based genetic clustering technique (Fuzzy-VGAPS) is proposed which can automatically determine the number of clusters present in a data set as well as a good fuzzy partitioning of the data. The clusters can be of any size, shape or convexity as long as they possess the property of symmetry. Here the membership values of points to different clusters are computed using the newly proposed point symmetry based distance. A variable number of cluster centers are encoded in the chromosomes. A new fuzzy symmetry based cluster validity index, FSym-index is first proposed here and thereafter it is utilized to measure the fitness of the chromosomes. The proposed index can detect non-convex, as well as convex-non-hyperspherical partitioning with variable number of clusters. It is mathematically justified via its relationship to a well-defined hard cluster validity function: the Dunn’s index, for which the condition of uniqueness has already been established. The results of the Fuzzy-VGAPS are compared with those obtained by seven other algorithms including both fuzzy and crisp methods on four artificial and four real-life data sets. Some real-life applications of Fuzzy-VGAPS to automatically cluster the gene expression data as well as segmenting the magnetic resonance brain image with multiple sclerosis lesions are also demonstrated.     

Isogeometric analysis and shape optimization via boundary integral

In this paper, we present a boundary integral based approach to isogeometric analysis and shape optimization.For analysis, it uses the same basis, Non-Uniform Rational B-Spline (NURBS) basis, for both representing object boundary and for approximating physical fields in analysis via a Boundary-Integral-Equation Method (BIEM). We propose the use of boundary points corresponding to Greville abscissae as collocation points. We conducted h-, p- and k-refinement study for linear elasticity and heat conduction problems. Our numerical experiments show that collocation at Greville abscissae leads to overall better convergence and robustness. Replacing rational B-splines with the linear B-Splines as shape functions for approximating solution space in analysis does not yield significant difference in convergence.For shape optimization, it uses NURBS control points to parameterize the boundary shape. A gradient based optimization approach is adopted where analytical sensitivities of how control points affect objective and constraint functions are derived. Two 3D shape optimization examples are demonstrated.Our study finds that the boundary integral based isogeometric analysis and optimization have the following advantages: (1) the NURBS based boundary integral exhibits superior computational advantages over the usual Lagrange polynomials based BIEM on a per degree-of-freedom basis; (2) it bypasses the need for domain parameterization, a bottleneck in current NURBS based volumetric isogeometric analysis and shape optimization; (3) it offers tighter integration of CAD and analysis since both the geometric models for both analysis and optimization are the same NURBS geometry.     

Efficient polygon decomposition into singular and regular regions via Voronoi diagrams

A new polygon decomposition into regular and singular regions is defined; it is a concept that is useful for skeleton extraction and part analysis of elongated shapes. Polygon regions that are narrow according to the Voronoi diagram of the polygon are extended through the boundary that is adjacent and quasiparallel. Regular regions are the narrow ones surrounded by smooth quasiparallel contour segments, while singular regions are the polygon regions that are not regular. We present an efficient algorithm to calculate the decomposition and make a comparative study with previous algorithms.Received: 21 December 2001, Accepted: 10 January 2003, Published online: 6 June 2003     

Segmentation of muscle cell pictures: a preliminary study

This paper describes a procedure for segmenting muscle cell pictures. The segmentation procedure is broken into two logical parts. The first part segments the picture into regions composed of cells or clumps of cells using a number of low-level operations. The second part of the procedure involves the segmentation of the cell clumps into individual cells. This is done by using a hierarchical clustering algorithm to group together those boundary points of a cell clump that belong to the same globally convex sections of the boundary. The dissimilarity measure used by the clustering algorithm is based only on information about the shape of the boundary, where this information is derived from line segments interior to the boundary. This procedure has given us satisfactory results on a number of test pictures.     

PCA-based 3D shape reconstruction of human foot using multiple viewpoint cameras

This paper describes a multiple camera-based method to reconstruct the 3D shape of a human foot. From a foot database, an initial 3D model of the foot represented by a cloud of points is built. The shape parameters, which can characterize more than 92% of a foot, are defined by using the principal component analysis method. Then, using ＂active shape models＂, the initial 3D model is adapted to the real foot captured in multiple images by applying some constraints （edge points＇ distance and color variance）. We insist here on the experiment part where we demonstrate the efficiency of the proposed method on a plastic foot model, and also on real human feet with various shapes. We propose and compare different ways of texturing the foot which is needed for reconstruction. We present an experiment performed on the plastic foot model and on human feet and propose two different ways to improve the final 3D shapers accuracy according to the previous experiments＇ results. The first improvement proposed is the densification of the cloud of points used to represent the initial model and the foot database. The second improvement concerns the projected patterns used to texture the foot. We conclude by showing the obtained results for a human foot with the average computed shape error being only 1.06 mm.     

CAD模型表面区域分割方法

三维模型表面区域分割技术在形状分析,尤其是局部形状分析中具有重要作用,传统的表面分割方法主要针对网格模型,而机械工程中的CAD模型通常用B-rep表达.提出一种B-rep形式的CAD模型表面区域分割方法,将模型表面划分为局部凸区域、凹区域和平区域的组合,并使得分割后的区域数量最少.为提高计算效率,提出一种二步法:首先在模型面的局部凸凹性分析的基础上,快速地将模型表面分割成初始的凸区域、凹区域和平区域;然后通过区域合并的方法对分割后的区域进行组合优化,得到一个最优的分割结果.实验结果证明,该方法能有效地分割模型的表面区域.     

On visual complexity of 3D shapes

We present an approach to compute the perceived complexity of a given 3D shape using the similarity between its views. Previous studies on 3D shape complexity relied on geometric and/or topological properties of the shape and are not appropriate for incorporating results from human shape perception which claim that humans perceive 3D shapes as organizations of 2D views. Therefore, we base our approach to computing 3D shape complexity on the (dis)similarity matrix of the shape's 2D views. To illustrate the application of our approach, we note that simple shapes lead to similar views whereas complex ones result in different, dissimilar views. This reflected in the View Similarity Graph (VSG) of a shape as tight clusters of points if the shape is simple and increasingly dispersed points as it gets more complex. To get a visual intuition of the VSG, we project it to 2D using Multi-Dimensional Scaling (MDS) and introduce measures to compute shape complexity through point dispersion in the resulting MDS plot. Experiments show that results obtained using our measures alleviate some of the drawbacks present in previous approaches.     

Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection

Given a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments. Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottom‐up by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log² n) operations are sufficient to compute the whole tree.     

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.