Applications of approximate string matching to 2D shape recognition

A new method for the recognition of arbitrary two-dimensional (2D) shapes is described. It is based on string edit distance computation. The recognition method is invariant under translation, rotation, scaling and partial occlusion. A set of experiments are described demonstrating the robustness and reliability of the proposed approach.     

基于Zernike形状矩的地图匹配算法

地图匹配算法的有效性和可靠性对于智能交通系统而言是非常重要的,而目前存在的地图匹配算法在一些复杂环境下（如道路交叉口）仍然不能提供合理的输出。采用D-S证据理论融合当前车辆位置信息和方向信息可以有效地扩大待匹配道路之间的差异,但在复杂路网下信息量的不足会降低其匹配精度。因此,为了提高道路网络中的地图匹配精度,提出了基于Zernike形状矩的地图匹配算法。新算法引入Zernike矩描述轨迹曲线的形状,进一步修正了错误结果。通过仿真和实验表明,新算法在复杂环境下具有较强的有效性和可靠性。     

基于粒子系统和形状匹配的实时无网格变形仿真

介绍了一种基于粒子系统和形状匹配的无网格变形算法。该算法将模型的每个顶点当成一个粒子,一个模型对应一个粒子系统,通过粒子系统控制物体外形。同时,每个粒子都对应一个目标位置,粒子与其目标位置之间存在弹力,能将粒子拉向目标位置,使得变形后的物体能够恢复原来的形状。目标位置可以通过粒子系统未变形时的静止状态与当前变形状态之间的形状匹配来计算。该算法简单,易于实现,且不需要复杂的数据结构。实验结果表明该算法稳定,具有实时性,可以有效地应用于三维游戏中。     

An elastic partial shape matching technique

We consider the problem of partial shape matching. We propose to transform shapes into sequences and utilize an algorithm that determines a subsequence of a target sequence that best matches a query. In the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a directed acyclic graph (DAG). The approach allows us to compute the optimal scale and translation of sequence values, which is a nontrivial problem in the case of subsequence matching. Our experimental results demonstrate that the proposed algorithm outperforms the commonly used techniques in retrieval accuracy.     

基于轮廓矢量化的形状匹配快速算法

针对现有形状匹配算法匹配速度慢、可靠性差的问题,提出了一种基于轮廓矢量化的形状匹配算法。将轮廓曲线点集离散化,使用多组向量对轮廓线性进行逼近。匹配时,结合线段在几何中的匹配方法,通过加权求和,计算源图像与目标图像中每组对应向量的相似度,将它们的平均值作为匹配结果。以焊盘表面轮廓为实验对象,使用所提出的算法进行匹配,结果表明,通过正确选取向量组数能有效避免匹配精度所受的影响,算法对不同类型的焊盘区分性较强,且匹配速度能满足实际应用的需要。     

基于范例匹配的卡通形象设计方法研究

针对动画卡通形象的特点,选取典型卡通形象范例,并分割出范例图元形成图元库。利用傅里叶形状描述方法统一描绘用户输入草图和范例图元的轮廓特征,用输入草图的特征检索图元库,得到相似的范例图元,通过交互方式调整和修改图元,进而生成个性化的卡通形象。实验结果表明,该方法生成的卡通形象基本符合用户的设计意图。     

基于特征融合的手形匹配算法

手形识别是生物特征识别的重要组成部分,手形匹配是手形识别的关键。目前常用的方法有特征矢量法（CVM）和点匹配方法（PPM）两种,这两种方法在对手形进行匹配时各有优点,也有局限性。提出一种多特征融合的手形识别算法,使得两者能够有效的结合起来,提高了手形匹配的准确性和鲁棒性。     

I形图的并的匹配等价图数

两个图[G]和[H]的匹配多项式相等,则称它们匹配等价。用[δ(G)]表示图[G]的所有不同构的匹配等价图的个数。[In(n6)]表示由路[Pn-4]的两个端点分 别粘接一个[P3]的2度点后得到的图。计算了一些[I]形图并图的匹配等价图的个数,即[δi∈AIi],这里[A]是一些大于等于6的整数组成的可重集。     

基于有向地形表面特征的尺度不变性地形匹配

针对条带地形的地形匹配定位,提出了航带地形的有向地形表面特征描述及匹配方法。在航带的一维方向上检测极值点,同时利用区域中心的极值点及其地形表面的切线作为参考,利用地形极值点相对于参考点和参考线的相对位置关系构造地形的具有不变性的特征,基于特征的距离计算和比较,实现了具有抵抗尺度变化等相似变换的地形匹配方法。仿真实验证明了该方法的有效性,对于从序列图像重建地形的匹配定位具有重要意义。     

Fingerprint matching using ridges

Traditionally, fingerprint matching is minutia-based, which establishes the minutiae correspondences between two fingerprints. In this paper, a novel fingerprint matching algorithm is presented, which establishes both the ridge correspondences and the minutia correspondences between two fingerprints. First N initial substructure (including a minutia and adjacent ridges) pairs are found by a novel alignment method. Based on each of these substructure pairs, ridge matching is performed by incrementally matching ridges and minutiae, and then a matching score is computed. The maximum one of the N scores is used as the final matching score of two fingerprints. Preliminary results on FVC2002 databases show that ridge matching approach performs comparably with the minutia-based one.     

基于IsoRank的三维耳廓形状匹配

基于IsoRank算法实现了耳廓剖分图的匹配,进而实现了基于耳廓三维形状的身份鉴别.基于主成分分析提取待匹配三维耳廓上的关键点,构造耳廓关键点的三维网格图;基于IsoRank算法求2个关键点三维网格图结点之间的对应关系,实现耳廓关键点的图匹配.由于采用了IsoRank算法,耳廓关键点网格图得到了全局对齐,两耳廓之间的整体匹配得到最大化.实验结果表明,基于IsoRank算法的耳廓匹配方法具有较低的时间复杂度以及较高的匹配精度和匹配效率.     

实时形状匹配变形体动画

给出了一个仿真变形体的方法。物体被几何方法推动变形,操纵基于点的物体并且不需要连接信息,这是一个不需要任何预处理,计算简单,并提供无条件稳定的动态仿真方法。主要思想是通过几何约束替换能量和通过当前位置到目标位置的距离替换力。这些目标位置通过一个通用的无变形的静止状态和点云的当前变形状态之间的形状匹配来决定,因为点总是在定义好的位置被绘制,显式积分方法的过度不稳定问题被消除。相关物体表现方法的灵活性能被控制,相关内存和计算是有效的,动态仿真上的无条件稳定性让这个方法特别适合游戏开发。     

双模态驱动的汉语语音与口型匹配控制模型

构建一种基于文本和朗读语音共同驱动的双模态语音与口型匹配控制模型,充分利用文本拼音提供正确的口型视位,利用朗读语音为口型视位提供正确的时序,在此基础上对口型几何参数和时间参数进行离散化,根据汉语语音发音机理,合理控制语音的口型动作过程。     

The partial model matching problem with stability

The Partial model matching problem has been initially introduced in Emre and Silverman (1980) and amounts to matching the first (k + 1) Markov parameters of the compensated plant with those of the model. We give here an algebraic and structural solution to this problem. Moreover, we give an answer to the stability question, which has remained open since then. As a possibly surprising result, we show that if this Partial problem is solvable, then there always exists a stable solution (provided the plant is stabilizable). We illustrate on a simple example how this objective can be realized in combination with some H_∞-norm attenuation. Limitations for the existence of static state feedback solutions are also discussed.     

Super-pattern matching

Some recognition problems are either too complex or too ambiguous to be expressed as a simple pattern matching problem using a sequence or regular expression pattern. In these cases, a richer environment is needed to describe the patterns and recognition techniques used to perform the recognition. Some researchers have turned to artificial-intelligence techniques and multistep matching approaches for the problems of gene recognition [5], [7], [18], protein structure recognition [13], and on-line character recognition [6]. This paper presents a class of problems which involve finding matches to patterns of patterns, orsuper- patterns, given solutions to the lower-level patterns. The expressiveness of this problem class rivals that of traditional artificial-intelligence characterizations, and yet polynomial-time algorithms are described for each problem in the class.This work was supported in part by the National Institute of Health under Grant ROI LM04960 and by the Aspen Center for Physics.     

Deformed template matching by the Viterbi algorithm

We consider a template matching algorithm that aims to deform a given template and place it onto a target-image to match as many edges as possible. To simplify this optimization problem, we will introduce a particular class of deformations that makes the Viterbi Algorithm applicative. To be specific, we will show how to describe a deformation by a a state-sequence, and how to find the optimally deformed template by the Viterbi Algorithm.     

A survey of content based 3D shape retrieval methods

Recent developments in techniques for modeling, digitizing and visualizing 3D shapes has led to an explosion in the number of available 3D models on the Internet and in domain-specific databases. This has led to the development of 3D shape retrieval systems that, given a query object, retrieve similar 3D objects. For visualization, 3D shapes are often represented as a surface, in particular polygonal meshes, for example in VRML format. Often these models contain holes, intersecting polygons, are not manifold, and do not enclose a volume unambiguously. On the contrary, 3D volume models, such as solid models produced by CAD systems, or voxels models, enclose a volume properly. This paper surveys the literature on methods for content based 3D retrieval, taking into account the applicability to surface models as well as to volume models. The methods are evaluated with respect to several requirements of content based 3D shape retrieval, such as: (1) shape representation requirements, (2) properties of dissimilarity measures, (3) efficiency, (4) discrimination abilities, (5) ability to perform partial matching, (6) robustness, and (7) necessity of pose normalization. Finally, the advantages and limitations of the several approaches in content based 3D shape retrieval are discussed.

Approximate string matching with suffix automata

Theapproximate string matching problem is, given a text string, a pattern string, and an integerk, to find in the text all approximate occurrences of the pattern. An approximate occurrence means a substring of the text with edit distance at mostk from the pattern. We give a newO(kn) algorithm for this problem, wheren is the length of the text. The algorithm is based on the suffix automaton with failure transitions and on the diagonalwise monotonicity of the edit distance table. Some experiments showing that the algorithm has a small overhead are reported.     

Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation

We present a 3D shape retrieval methodology based on the theory of spherical harmonics. Using properties of spherical harmonics, scaling and axial flipping invariance is achieved. Rotation normalization is performed by employing the continuous principal component analysis along with a novel approach which applies PCA on the face normals of the model. The 3D model is decomposed into a set of spherical functions which represents not only the intersections of the corresponding surface with rays emanating from the origin but also points in the direction of each ray which are closer to the origin than the furthest intersection point. The superior performance of the proposed methodology is demonstrated through a comparison against state-of-the-art approaches on standard databases.