形状的圆内距离变换

目的 形状的描述、匹配、相似性判定和检索是计算机视觉和图像识别的基本问题,也是一个开问题。在目前公开的方法中,除了只能应用于简单形状的几何复变换和基于边界的傅里叶描述子外,其他的方法均不能由构建的形状特征描述符重建原形状,因此不能保证所建立的形状特征能客观地描述原形状。本文提出了形状的圆内距离变换,该方法所建立的描述符可用于形状匹配、相似性度量和形状检索。该方法是可逆的,也就是可以从形状描述符重建原形状。方法 形状的圆内距离变换通过在形状的最小外接圆内旋转和切分形状,求出形状相邻切分点之间的距离,并由此构建形状的特征矩阵。对于任意相似的形状,从理论上证明了形状的圆内距离变换具有缩放、旋转和位移不变性。结果 对发生了形变、扭曲和仿射变换的形状,采用圆内距离变换方法进行了形状的相似性度量、检索和重建实验,结果表明,形状的圆内距离变换可以准确地描述形状、度量形状的相似性、检索形状并重建原形状。在形状的相似性度量上,形状的圆内距离变换能给出与人类视觉一致的结果,并且当两个形状相似时,还能计算出它们的尺度缩放和角度旋转。通过与经典的方法,包括形状上下文方法、傅里叶描述子方法、拉东柱状图方法,针对典型的MPEG-7形状库进行对比实验,发现形状的圆内距离变换在形状检索的综合得分上相比这些经典方法提高了近20%。结论 形状的圆内距离变换在形状的描述、相似性判定和检索上是有效和可逆的,具有广泛的可适用性且优于本文比较的其他经典方法。     

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.     

使用形状变化描述三维模型

针对三维模型检索中的形状特征提取问题,提出利用三维模型自身形状变化信息构造形状特征描述符的方法.首先选择一组等间距互相平行的平面切割三维模型,得到三维模型的切片集合;然后定义相邻切片的 差来描述切片间的形状变化,并通过所有相邻切片间的差值来反映三维模型自身的形状变化,以此作为三维模型的形状特征描述符.该方法与三维模型的旋转、平移无关,同时不依赖于模型的点云分布,并且精简模型三角面片对算法的影响较小.实验结果验证了该方法的有效性.     

典型的基于区域的形状表示方法比较

目的 形状的表示和匹配是计算机视觉和模式识别领域的重要问题。在基于区域的形状表示方法中出现了一批典型的方法,包括Hu不变矩方法（Hu不变矩）、角径向变换方法（ART方法）、通用傅里叶描述子方法（GFD方法）、拉东柱状图方法（HRT方法）和多尺度积分不变量方法（MSⅡ方法）等。由于这些方法出现的时间跨度长且在以往的对比研究中研究维度单一,因此需要对这些方法的综合性能做一个全面的比较分析和研究,为下一步的理论研究和实际应用提供方向和指导。方法 采用3个基准形状库,包括简单几何图形形状库、MPEG-7形状库和汽车商标形状库,从3个维度,包括检索得分、检索稳定性和方法的计算复杂度,使用加权综合评估模型对典型的基于区域的形状表示方法进行比较分析,综合评估各种方法的综合性能指标。结果 在综合性能上GFD方法具有最优的效果,其次是ART方法;由于HRT方法在匹配计算阶段具有较高的时间复杂度,在大规模形状库匹配的场景下性能会下降;Hu不变矩和MSⅡ方法的实验效果均不理想。通过比较研究还发现,将形状正交投影到正交基函数是提取形状视觉特征的有效方式。进一步猜想,将图像正交投影到正交基函数也是提取图像视觉特征的有效方式。因此,未来的研究中,寻找理想的正交基函数是提取形状乃至图像视觉特征的重要研究方向。结论 在5种比较研究的方法中,GFD方法和ART方法在综合效果要好于HRT方法、Hu不变矩方法和MSⅡ方法,并且寻找理想的正交基函数是未来形状表示的重要研究方向。     

Recognition of shapes by attributed skeletal graphs

In this paper, we propose a framework to address the problem of generic 2-D shape recognition. The aim is mainly on using the potential strength of skeleton of discrete objects in computer vision and pattern recognition where features of objects are needed for classification. We propose to represent the medial axis characteristic points as an attributed skeletal graph to model the shape. The information about the object shape and its topology is totally embedded in them and this allows the comparison of different objects by graph matching algorithms. The experimental results demonstrate the correctness in detecting its characteristic points and in computing a more regular and effective representation for a perceptual indexing. The matching process, based on a revised graduated assignment algorithm, has produced encouraging results, showing the potential of the developed method in a variety of computer vision and pattern recognition domains. The results demonstrate its robustness in the presence of scale, reflection and rotation transformations and prove the ability to handle noise and occlusions.     

Knowledge-based part correspondence

This paper presents a direct method for finding corresponding pairs of parts between two shapes. Statistical knowledge about a large number of parts from many different objects is used to find a part correspondence between two previously unseen input shapes. No class membership information is required. The knowledge-based approach is shown to produce significantly better results than a classical metric distance approach. The potential role of part correspondence as a complement to geometric and structural comparisons is discussed.     

Shape modeling and matching in identifying 3D protein structures

In this paper, we describe a novel geometric approach in the process of recovering 3D protein structures from scalar volumes. The input to our method is a sequence of α-helices that make up a protein, and a low-resolution protein density volume where possible locations of α-helices have been detected. Our task is to identify the correspondence between the two sets of helices, which will shed light on how the protein folds in space. The central theme of our approach is to cast the correspondence problem as that of shape matching between the 3D volume and the 1D sequence. We model both shapes as attributed relational graphs, and formulate a constrained inexact graph matching problem. To compute the matching, we developed an optimal algorithm based on the A*-search with several choices of heuristic functions. As demonstrated in a suite of synthetic and authentic inputs, the shape-modeling approach is capable of identifying helix correspondences in noise-abundant volumes at high accuracy with minimal or no user intervention.     

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.     

结合谱变换和马尔可夫模型的三维形状对齐

针对大尺度变形下的三维形状对齐问题,提出根据三维形状的等距性构造马尔可夫能量最小化模型,得到最优对齐结果。算法对三维模型进行谱变换,在变换空间中对三维模型进行初始化对齐。以谱距离和测地距离分别定义马尔可夫模型的单点势能函数和点对势能函数,形成可用于形状对齐的能量最小化模型。通过Alpha扩展算法对模型进行求解,得到最终的对齐结果。实验结果表明,算法在大尺度变形和拓扑变化等情况都能够输出很好的对齐结果。     

带有未知匹配的图像线特征三维重建方法的研究*

为了解决传统三维重建过程中线特征匹配速度慢、建模与匹配过程脱节的问题,提出了基于相关系数的图像线特征匹配的方法,运用此方法对同一物体的三幅图像进行了特征匹配和三维重建。建立了目标物体的三维模型,达到了对物体线特征匹配与三维重建同步进行的目的。通过对所得实验数据分析,可以证明此算法对于物体的三维重建是有效的。     

Dissimilarity between two skeletal trees in a context

Skeletal trees are commonly used in order to express geometric properties of the shape. Accordingly, tree-edit distance is used to compute a dissimilarity between two given shapes. We present a new tree-edit based shape matching method which uses a recent coarse skeleton representation. The coarse skeleton representation allows us to represent both shapes and shape categories in the form of depth-1 trees. Consequently, we can easily integrate the influence of the categories into shape dissimilarity measurements. The new dissimilarity measure gives a better within group versus between group separation, and it mimics the asymmetric nature of human similarity judgements.     

A fast algorithm for ICP-based 3D shape biometrics

In a biometrics scenario, gallery images are enrolled into the database ahead of the matching step, which gives us the opportunity to build related data structures before the probe shape is examined. In this paper, we present a novel approach, called “Pre-computed Voxel Nearest Neighbor”, to reduce the computational time for shape matching in a biometrics context. The approach shifts the heavy computation burden to the enrollment stage, which is done offline. Experiments in 3D ear biometrics with 369 subjects and 3D face biometrics with 219 subjects demonstrate the effectiveness of our approach.     

Automatic layout of 2D free-form shapes based on geometric similarity feature searching and fuzzy matching

Two-dimensional (2D) irregular layout is widely applied in various manufacturing processes, such as sheet metal cutting, shipbuilding, and electronic component placement. An efficient layout algorithm can effectively improve the material utilization, thereby reducing manufacturing cost. But the free-form shape layout problem is very challenge as it is difficult to exactly represent a free-form shape. There is not an efficient method currently available for the 2D free-form shape layout. This paper proposes a method based on the geometric similarity feature searching and fuzzy matching for the 2D free-form shape layout. The freeman chain code is developed to describe the contour information of shapes and forward-lines to form the basis of the layout strategy. A strategy based on fuzzy matching is proposed for the layout, which includes searching geometric similarity features using the longest common subsequence and the proposed placement algorithm to complete the collision. Three computational experiments are conducted to analyze the performance of the proposed method. Experimental results show that the proposed method is feasible and effective with the good applicability to achieve a high filling rate in reduced time.