Generalizing the Hough transform to detect arbitrary shapes

The Hough transform is a method for detecting curves by exploiting the duality between points on a curve and parameters of that curve. The initial work showed how to detect both analytic curves^(1,2) and non-analytic curves,⁽³⁾ but these methods were restricted to binary edge images. This work was generalized to the detection of some analytic curves in grey level images, specifically lines,⁽⁴⁾ circles⁽⁵⁾ and parabolas.⁽⁶⁾ The line detection case is the best known of these and has been ingeniously exploited in several applications.^(7,8,9)We show how the boundaries of an arbitrary non-analytic shape can be used to construct a mapping between image space and Hough transform space. Such a mapping can be exploited to detect instances of that particular shape in an image. Furthermore, variations in the shape such as rotations, scale changes or figure ground reversals correspond to straightforward transformations of this mapping. However, the most remarkable property is that such mappings can be composed to build mappings for complex shapes from the mappings of simpler component shapes. This makes the generalized Hough transform a kind of universal transform which can be used to find arbitrarily complex shapes.     

Application of planar shape comparison to object retrieval in image databases

A similarity measure for silhouettes of 2D objects is presented, and its properties are analyzed with respect to retrieval of similar objects in image databases. To reduce influence of digitization noise as well as segmentation errors the shapes are simplified by a new process of digital curve evolution. To compute our similarity measure, we first establish the best possible correspondence of visual parts (without explicitly computing the visual parts). Then the similarity between corresponding parts is computed and summed. Experimental results show that our shape matching procedure gives an intuitive shape correspondence and is stable with respect to noise distortions.     

Deformation similarity measurement in quasi-conformal shape space

This paper presents a novel approach based on the shape space concept to classify deformations of 3D models. A new quasi-conformal metric is introduced which measures the curvature changes at each vertex of each pose during the deformation. The shapes with similar deformation patterns follow a similar deformation curve in shape space. Energy functional of the deformation curve is minimized to calculate the geodesic curve connecting two shapes on the shape space manifold. The geodesic distance illustrates the similarity between two shapes, which is used to compute the similarity between the deformations. We applied our method to classify the left ventricle deformations of myopathic and control subjects, and the sensitivity and specificity of our method were 88.8% and 85.7%, which are higher than other methods based on the left ventricle cavity, which shows our method can quantify the similarity and disparity of the left ventricle motion well.     

Arithmetic operations among shapes using shape numbers

In this work, a notation is given called the Discrete Geometry of Shapes, which describes the forms or shapes of flat regions limited by simply connected curves. A procedure is given that deduces from every region a unique number (its shape number) independent of translation and rotation, and optionally, of size and origin.All the integer numbers contain all the universe of discrete shapes (of course with different precision). In this universe there are shapes such as straight lines, circumferences, ellipses, parabolas, trigonometric functions, graphics of time, absorption waves, etc.The Discrete Geometry of Shapes is one-dimensional. It does not use the definition of equation and function to define shapes in a rectangular co-ordinate plane. With this notation it is possible to generate shapes with any characteristics by generating numerical sequences; also it is possible to do arithmetic operations among shapes. For example, the addition of a square and a circle, the average of a triangle and a circle, the square root of a pentagon, the numerical relations between given shapes, etc.Section V of this work describes the third dimension in the Discrete Geometry of Shapes for surfaces and volumes by means of a vector of shape numbers. It is possible to add surfaces, to divide volumes, to obtain the square root of a volume, etc.The main objective of this notation is the simplification of some mathematical and geometrical processes in this analysis of shapes and surfaces.     

三次均匀B样条曲线的新扩展及应用

给出了一组含有2个形状参数λ_i,μ_i的三次多项式调配函数,它是三次均匀B样条基函数的扩展;分析了这组调配函数的性质,基于此组调配函数定义了一种带2个局部形状控制参数λ_i,μ_i的分段多项式样条曲线,它以三次均匀B样条曲线为特殊情形。新曲线不仅具有灵活的局部形状可调性和更强的描述能力,而且可以在不改变曲线G¹连续性和不影响曲线其他各段形状的同时,通过改变局部形状参数对曲线每段的形状进行多种方式的局部调整。最后讨论了新曲线在曲线造型中的应用,并给出了一个扩展曲面的定义。实例表明,新扩展曲线为曲线/曲面的设计提供了一种有效的新方法。     

Order-k α-hulls and α-shapes

We introduce order-k α-hulls and α-shapes – generalizations of α-hulls and α-shapes. Being also a generalization of k-hull (known in statistics as “k-depth contour”), order-k α-hull provides a link between shape reconstruction and statistical depth. As a generalization of α-hull, order-k α-hull gives a robust shape estimation by ignoring locally up to k outliers in a point set. Order-k α-shape produces an “inner” shape of the set, with the amount of “digging” into the points controlled by k. As a generalization of k-hull, order-k α-hull is capable of determining “deep” points amidst samples from a multimodal distribution: it correctly identifies points which lie outside clusters of samples.The order-k α-hulls and α-shapes are related to order-k Voronoi diagrams in the same way in which α-hulls and α-shapes are related to Voronoi diagrams. This implies that order-k α-hull and α-shape can be readily built from order-k Voronoi diagram, and that the number of different order-k α-shapes for all possible values of α is proportional to the complexity of order-k Voronoi diagram.     

An A Contrario Decision Method for Shape Element Recognition

Shape recognition is the field of computer vision which addresses the problem of finding out whether a query shape lies or not in a shape database, up to a certain invariance. Most shape recognition methods simply sort shapes from the database along some (dis-)similarity measure to the query shape. Their main weakness is the decision stage, which should aim at giving a clear-cut answer to the question: “do these two shapes look alike?” In this article, the proposed solution consists in bounding the number of false correspondences of the query shape among the database shapes, ensuring that the obtained matches are not likely to occur “by chance”. As an application, one can decide with a parameterless method whether any two digital images share some shapes or not.     

Geometric Flows of Curves in Shape Space for Processing Motion of Deformable Objects

We introduce techniques for the processing of motion and animations of non‐rigid shapes. The idea is to regard animations of deformable objects as curves in shape space. Then, we use the geometric structure on shape space to transfer concepts from curve processing in ?ⁿ to the processing of motion of non‐rigid shapes. Following this principle, we introduce a discrete geometric flow for curves in shape space. The flow iteratively replaces every shape with a weighted average shape of a local neighborhood and thereby globally decreases an energy whose minimizers are discrete geodesics in shape space. Based on the flow, we devise a novel smoothing filter for motions and animations of deformable shapes. By shortening the length in shape space of an animation, it systematically regularizes the deformations between consecutive frames of the animation. The scheme can be used for smoothing and noise removal, e.g., for reducing jittering artifacts in motion capture data. We introduce a reduced‐order method for the computation of the flow. In addition to being efficient for the smoothing of curves, it is a novel scheme for computing geodesics in shape space. We use the scheme to construct non‐linear “Bézier curves” by executing de Casteljau's algorithm in shape space.     

拱序列的曲线描述与匹配

目的 曲线匹配是计算机视觉和图像处理中的一个重要问题;判定几何图形形状相似性,得到与人类认知一致的结果,是目前的曲线描述与分类算法不能很好解决的问题。针对曲线匹配和几何图形形状的相似性判定,提出一种有效快速的基于拱序列的曲线匹配与相似性判定算法。方法 提取曲线的角点,将曲线表示为一连串相互重叠的拱序列。对于拱序列中的每一个拱,使用拱描述子进行描述。利用拱描述子,使用动态规划方法,实现对拱序列的匹配和相似性判定。结果 为了验证本文算法,将基于拱序列的曲线描述与匹配方法应用于轮廓的拼接与几何图形的相似性比较。在轮廓拼接实验中,基于拱序列的曲线描述与匹配方法准确完成碎片轮廓的拼接和地图轮廓的拼接。在几何图形相似性的交叉度量实验中,基于拱序列的曲线描述与匹配方法可以准确反映出图形的相似程度,正确判断两幅图像是否属于同一类型。在判定不同相似程度的形状对的实验中,本文算法可以给出与人类判断相同的结果,相比较基于链码特征、多尺度不变量、形状上下文和GCT（geometry complex transform）变换算法,本文算法的距离值更好地反映出图像的相似程度。结论 理论和实验表明,该算法可有效地描述曲线、匹配曲线,及准确判断几何图形的相似性,给出与人类视觉判定一致的结果。该算法可用于基于轮廓的图像拼接和几何图形相似性的判定。     

Geometry curves: A compact representation for 3D shapes

We propose a novel compact surface representation, namely geometry curves, which record the essence of shape geometry and topology. The geometry curves mainly contain two parts: the interior and boundary lines. The interior lines, which correspond to the feature lines, record the geometry information of the 3D shapes; the boundary lines, which correspond to the boundary or fundamental polygons, record the topology information of the 3D shapes. As a vector representation, geometry curves can depict highly complex geometry details. The concept of geometry curves can be utilized in many potential applications, e.g., mesh compression, shape modeling and editing, animation, and level of details. Furthermore, we develop a procedure for automatically constructing geometry curves which obtain an excellent approximation to the original mesh.     

Notes on shape orientation where the standard method does not work

In this paper we consider some questions related to the orientation of shapes with particular attention to the situation where the standard method does not work. There are irregular and non-symmetric shapes whose orientation cannot be computed in a standard way, but in the literature the most studied situations are those where the shape under consideration has more than two axes of symmetry or where it is an n-fold rotationally symmetric shape with n>2. The basic reference for our work is [W.H. Tsai, S.L. Chou, Detection of generalized principal in rotationally symmetric shapes, Pattern Recognition 24 (1991) 95-104]. We give a very simple proof of the main result from [W.H. Tsai, S.L. Chou, Detection of generalized principal in rotationally symmetric shapes, Pattern Recognition 24 (1991) 95-104] and suggest a modification of the proposal on how the principal axes of rotationally symmetric shapes should be computed. We show some desirable property in defining the orientation of such shapes if the modified approach is applied. Also, we give some comments on the problems that arise when computing shape elongation.     

A class of general quartic spline curves with shape parameters

With a support on four consecutive subintervals, a class of general quartic splines are presented for a non-uniform knot vector. The splines have C² continuity at simple knots and include the cubic non-uniform B-spline as a special case. Based on the given splines, piecewise quartic spline curves with three local shape parameters are given. The given spline curves can be C²∩G³ continuous by fixing some values of the curve?s parameters. Without solving a linear system, the spline curves can also be used to interpolate sets of points with C² continuity. The effects of varying the three shape parameters on the shape of the quartic spline curves are determined and illustrated.     

Hierarchical part-type segmentation using voxel-based curve skeletons

We present an effective framework for segmenting 3D shapes into meaningful components using the curve skeleton. Our algorithm identifies a number of critical points on the efficiently computed curve skeleton, either fully automatically as the junctions of the curve skeleton, or based on user input. We use these points to construct a partitioning of the object surface using geodesics. Because the segmentation is based on the curve skeleton, it intrinsically reflects the shape symmetry and articulation, and can handle shapes with tunnels. We describe a voxel-based implementation of our method which is robust and noise resistant, able to handle shapes of complex articulation and topology, produces smooth segment borders, and delivers hierarchical level-of-detail segmentations. We demonstrate the framework on various real-world 3D shapes. Additionally, we discuss the use of both curve and surface skeletons to produce part-type and patch-type, respectively, segmentations of 3D shapes.     

对可调控Bézier曲线的改进

目的 在用Bézier曲线表示复杂形状时,相邻曲线的控制顶点间必须满足一定的光滑性条件。一般情况下,对光滑度的要求越高,条件越复杂。通过改进文献中的“可调控Bézier曲线”,以构造具有多种优点的自动光滑分段组合曲线。方法 首先给出了两条位置连续的曲线G^l连续的一个充分条件,进而证明了“可调控Bézier曲线”在普通Bézier曲线的G^l光滑拼接条件下可达G^l(l为曲线中的参数)光滑拼接。然后对“可调控Bézier基”进行改进得到了一组新的基函数,利用该基函数按照Bézier曲线的定义方式构造了一种新曲线。分析了该曲线的光滑拼接条件,并根据该条件定义了一种分段组合曲线。结果 对于新曲线而言,只要前一条曲线的最后一条控制边与后一条曲线的第1条控制边重合,两条曲线便自动光滑连接,并且在连接点处的光滑度可以简单地通过改变参数的值来自由调整。由新曲线按照特殊方式构成的分段组合曲线具有类似于B样条曲线的自动光滑性和局部控制性。不同的是,组合曲线的各条曲线段可以由不同数量的控制顶点定义,选择合适的参数,可以使曲线在各个连接点处达到任何期望的光滑度。另外,改变一个控制顶点,至多只会影响两条曲线段的形状,改变一条曲线段中的参数,只会影响当前曲线段的形状,以及至多两个连接点处的光滑度。结论 本文给出了构造易于拼接的曲线的通用方法,极大简化了曲线的拼接条件。此基础上,提出的一种新的分段组合曲线定义方法,无需对控制顶点附加任何条件,所得曲线自动光滑,且其形状、光滑度可以或整体或局部地进行调整。本文方法具有一般性,为复杂曲线的设计创造了条件。     

An Optimization Approach to Improving Collections of Shape Maps

Finding an informative, structure‐preserving map between two shapes has been a long‐standing problem in geometry processing, involving a variety of solution approaches and applications. However, in many cases, we are given not only two related shapes, but a collection of them, and considering each pairwise map independently does not take full advantage of all existing information. For example, a notorious problem with computing shape maps is the ambiguity introduced by the symmetry problem — for two similar shapes which have reflectional symmetry there exist two maps which are equally favorable, and no intrinsic mapping algorithm can distinguish between them based on these two shapes alone. Another prominent issue with shape mapping algorithms is their relative sensitivity to how “similar” two shapes are — good maps are much easier to obtain when shapes are very similar. Given the context of additional shape maps connecting our collection, we propose to add the constraint of global map consistency, requiring that any composition of maps between two shapes should be independent of the path chosen in the network. This requirement can help us choose among the equally good symmetric alternatives, or help us replace a “bad” pairwise map with the composition of a few “good” maps between shapes that in some sense interpolate the original ones. We show how, given a collection of pairwise shape maps, to define an optimization problem whose output is a set of alternative maps, compositions of those given, which are consistent, and individually at times much better than the original. Our method is general, and can work on any collection of shapes, as long as a seed set of good pairwise maps is provided. We demonstrate the effectiveness of our method for improving maps generated by state‐of‐the‐art mapping methods on various shape databases.     

Visual rendering of shapes on 2D display devices guided by hand gestures

Designing of touchless user interface is gaining popularity in various contexts. Users can interact with electronic devices using such interfaces even when their hands are dirty or non-conductive. Also, users with partial physical disability can interact with electronic devices with the help of touchless interfaces. In this paper, we propose a Leap Motion controller-based methodology to facilitate rendering of 2D and 3D shapes on display devices. The proposed method tracks finger movements while users perform natural gestures within the field of view of the motion sensor. Then, trajectories are analyzed to extract extended Npen++ features in 3D. These features capture finger movements during the gestures and they are fed to unidirectional left-to-right Hidden Markov Model (HMM) for training. A one-to-one mapping between gestures and shapes, is proposed. Finally, the shapes corresponding to these gestures are rendered over the display using a typical MuPad supported interface. We have created a dataset of 5400 samples recorded by 10 volunteers. Our dataset contains 18 geometric and 18 non-geometric shapes such as “circle”, “rectangle”, “flower”, “cone”, “sphere”, etc. The proposed method has achieved 92.87% accuracy using a 5-fold cross validation scheme. Experiments reveal that the extended 3D features perform better than the existing 3D features when applied for shape representation and classification. The method can be used for developing diverse HCI applications suitable for smart display devices.     

2D-Shape Analysis Using Conformal Mapping

The study of 2D shapes and their similarities is a central problem in the field of vision. It arises in particular from the task of classifying and recognizing objects from their observed silhouette. Defining natural distances between 2D shapes creates a metric space of shapes, whose mathematical structure is inherently relevant to the classification task. One intriguing metric space comes from using conformal mappings of 2D shapes into each other, via the theory of Teichmüller spaces. In this space every simple closed curve in the plane (a “shape”) is represented by a ‘fingerprint’ which is a diffeomorphism of the unit circle to itself (a differentiable and invertible, periodic function). More precisely, every shape defines to a unique equivalence class of such diffeomorphisms up to right multiplication by a Möbius map. The fingerprint does not change if the shape is varied by translations and scaling and any such equivalence class comes from some shape. This coset space, equipped with the infinitesimal Weil-Petersson (WP) Riemannian norm is a metric space. In this space, the shortest path between each two shapes is unique, and is given by a geodesic connecting them. Their distance from each other is given by integrating the WP-norm along that geodesic. In this paper we concentrate on solving the “welding” problem of “sewing” together conformally the interior and exterior of the unit circle, glued on the unit circle by a given diffeomorphism, to obtain the unique 2D shape associated with this diffeomorphism. This will allow us to go back and forth between 2D shapes and their representing diffeomorphisms in this “space of shapes”. We then present an efficient method for computing the unique shortest path, the geodesic of shape morphing between each two end-point shapes. The group of diffeomorphisms of S¹ acts as a group of isometries on the space of shapes and we show how this can be used to define shape transformations, like for instance ‘adding a protruding limb’ to any shape.     

Partial shape-preserving splines

A complex geometric shape is often a composition of a set of simple ones, which may differ from each other in terms of their mathematical representations and the ways in which they are constructed. One of the necessary requirements in combining these simple shapes is that their original shapes can be preserved as much as possible. In this paper, a set of partial shape-preserving (PSP) spline basis functions is introduced to smoothly combine a collection of shape primitives with flexible blending range control. These spline basis functions can be considered as a kind of generalization of traditional B-spline basis functions, where the shape primitives used are control points or control polygons. The PSP-spline basis functions have all the advantages of the conventional B-spline technique in the sense that they are nonnegative, piecewise polynomial and of property of partition of unity. However, PSP-spline is a more powerful freeform geometric shape design technique in the sense that it is also a kind of shape-preserving spline. In addition, the PSP-spline technique implicitly integrates the weights of shape control primitives into its basis functions, which allows users to design a required geometric shape based on weighted control primitives. Though its basis functions are simply piecewise polynomial functions, it has the same shape design strengths as the rational piecewise polynomial based spline techniques such as NURBS. In particular, when control shape primitives are specified as a set of control points, PSP-spline behaves like a polygon smoother, with which a shape can be designed to approximate the specified control polygon or control mesh smoothly with any required precision. Consequently, a richer set of geometric shapes can be built using a relatively smaller set of control points.