Shape recognition based on Kernel-edit distance

In this paper a kernel method for shape recognition is proposed. The approach is based on the edit distance between pairs of shapes after transforming them into symbol strings. The transformation of shapes into symbol strings is invariant to similarity transforms and can handle partial occlusions. Representation of shape contours uses the shape contexts and applies dynamic programming for finding the correspondence between points over shape contours. Corresponding points are then transformed into symbolic representation and the normalized edit distance computes the dissimilarity between pairs of strings in the database. Obtained distances are then transformed into suitable kernels which are classified using support vector machines. Experimental results over a variety of shape databases show that the proposed approach is suitable for shape recognition.     

PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance

We consider the problem of PAC-learning distributions over strings, represented by probabilistic deterministic finite automata (PDFAs). PDFAs are a probabilistic model for the generation of strings of symbols, that have been used in the context of speech and handwriting recognition, and bioinformatics. Recent work on learning PDFAs from random examples has used the KL-divergence as the error measure; here we use the variation distance. We build on recent work by Clark and Thollard, and show that the use of the variation distance allows simplifications to be made to the algorithms, and also a strengthening of the results; in particular that using the variation distance, we obtain polynomial sample size bounds that are independent of the expected length of strings.     

Recognition by linear combinations of models

An approach to visual object recognition in which a 3D object is represented by the linear combination of 2D images of the object is proposed. It is shown that for objects with sharp edges as well as with smooth bounding contours, the set of possible images of a given object is embedded in a linear space spanned by a small number of views. For objects with sharp edges, the linear combination representation is exact. For objects with smooth boundaries, it is an approximation that often holds over a wide range of viewing angles. Rigid transformations (with or without scaling) can be distinguished from more general linear transformations of the object by testing certain constraints placed on the coefficients of the linear combinations. Three alternative methods of determining the transformation that matches a model to a given image are proposed     

Contour Tracking in Clutter: A Subset Approach

A new method for tracking contours of moving objects in clutter is presented. For a given object, a model of its contours is learned from training data in the form of a subset of contour space. Greater complexity is added to the contour model by analyzing rigid and non-rigid transformations of contours separately. In the course of tracking, multiple contours may be observed due to the presence of extraneous edges in the form of clutter; the learned model guides the algorithm in picking out the correct one. The algorithm, which is posed as a solution to a minimization problem, is made efficient by the use of several iterative schemes. Results applying the proposed algorithm to the tracking of a flexing finger and to a conversing individual's lips are presented.     

Portrep: A portable repeated string finder

In recent years, several authors have presented algorithms that locate instances of a given string, or set of strings, within a text. Recently, authors have given less consideration to the complementary problem of processing a text to find out what strings appear in the text, without any preconceived notion of what strings might be present. A system called PATRICIA, which was developed two decades ago, is an implementation of a solution to this problem. The design of PATRICIA is very tightly bound to the assumptions that individual string elements are bits and that the user of the system can provide complete lists of starting and stopping places for strings. This paper presents an approach that drops these assumptions. Our method allows different definitions of indivisible string elements for different applications, and the only information the user provides for the determination of the beginning and ends of strings is a specification of a maximum length for output strings. This paper also describes a portable C implementation of the method, called PORTREP. The primary data structure of PORTREP is a trie represented as a ternary tree. PORTREP has a method for eliminating redundancy from the output, and it can function with a bounded number of nodes by employing a heuristic process that reuses seldom-visited nodes. Theoretical analysis and empirical studies, reported here, give confidence in the efficiency of the algorithms. PORTREP has the ability to form the basis for a variety of text-analysis applications, and this paper considers one such application, automatic document indexing.     

基于串核的音乐分类研究

给出了一种新的映射音乐到Rn空间的方法和基于串核的音乐风格分类法。首先利用统计方法分析大量音乐的旋律轮廓线得到合适的编码模式,用它把旋律轮廓线编码为有限字母表（8个字母）的字符串。利用连续子串嵌入法把音乐串显式映射到高维Rn空间,并用核表示这一映射。通过用基于核的SVM分类算法和ROC评价方法,比较了3个不同串核在5组音乐数据集上的分类性能。     

Anatomical structure modeling from medical images

Some clinical applications, such as surgical planning, require volumetric models of anatomical structures represented as a set of tetrahedra. A practical method of constructing anatomical models from medical images is presented. The method starts with a set of contours segmented from the medical images by a clinician and produces a model that has high fidelity with the contours. Unlike most modeling methods, the contours are not restricted to lie on parallel planes. The main steps are a 3D Delaunay tetrahedralization, culling of non-object tetrahedra, and refinement of the tetrahedral mesh. The result is a high-quality set of tetrahedra whose surface points are guaranteed to match the original contours. The key is to use the distance map and bit volume structures that were created along with the contours. The method is demonstrated on computed tomography, MRI and 3D ultrasound data. Models of 170,000 tetrahedra are constructed on a standard workstation in approximately 10s. A comparison with related methods is also provided.     

On Shape of Plane Elastic Curves

We study shapes of planar arcs and closed contours modeled on elastic curves obtained by bending, stretching or compressing line segments non-uniformly along their extensions. Shapes are represented as elements of a quotient space of curves obtained by identifying those that differ by shape-preserving transformations. The elastic properties of the curves are encoded in Riemannian metrics on these spaces. Geodesics in shape spaces are used to quantify shape divergence and to develop morphing techniques. The shape spaces and metrics constructed are novel and offer an environment for the study of shape statistics. Elasticity leads to shape correspondences and deformations that are more natural and intuitive than those obtained in several existing models. Applications of shape geodesics to the definition and calculation of mean shapes and to the development of shape clustering techniques are also investigated.     

基于串核的音乐风格聚类

给出了一种新的映射音乐到R°空间的方法和基于串核的音乐风格聚类法.利用统计方法分析大量音乐的旋律轮廓线得到合适的编码模式,用它把旋律轮廓线编码为有限字母表(8个字母)的字符串.利用连续子串嵌入法把音乐串显式映射到高维R°空间,并用核表示这一映射.通过用基于核的山方法选择聚类的适合初始点,最后使用基于核的K-means方法聚类音乐数据集,比较了3个不同串核在5个音乐数据集上的聚类性能.     

Genetic algorithms and neural networks: optimizing connections and connectivity

Genetic algorithms are a robust adaptive optimization method based on biological principles. A population of strings representing possible problem solutions is maintained. Search proceeds by recombining strings in the population. The theoretical foundations of genetic algorithms are based on the notion that selective reproduction and recombination of binary strings changes the sampling rate of hyperplanes in the search space so as to reflect the average fitness of strings that reside in any particular hyperplane. Thus, genetic algorithms need not search along the contours of the function being optimized and tend not to become trapped in local minima. This paper is an overview of several different experiments applying genetic algorithms to neural network problems. These problems include

1. (1) optimizing the weighted connections in feed-forward neural networks using both binary and real-valued representations, and

2. (2) using a genetic algorithm to discover novel architectures in the form of connectivity patterns for neural networks that learn using error propagation.

Future applications in neural network optimization in which genetic algorithm can perhaps play a significant role are also presented.     

Compact object recognition using energy-function-based optimization

Describes a method of recognizing objects whose contours can be represented in smoothly varying polar coordinate form. Both low- and high-level information about the object (contour smoothness and edge sharpness at the low level and contour shape at the high level) are incorporated into a single energy function that defines a 1D, cyclic, Markov random field (1DCMRF). This 1DCMRF is based on a polar coordinate object representation whose center can be initialized at any location within the object. The recognition process is based on energy function minimization, which is implemented by simulated annealing     

A method for graphic stress representation

Stress representation by coloured patterns and contours through the use of the finite element method is presented in this paper. Stresses are computed in the center of each subregion defined in the element surface being displayed. These stresses define a matrix of codes related to the “stress bands” which must be represented. This matrix is used to “paint” every subregion and to generate contours defined by points located between two adjacent subregions of different codes. Some examples are presented to show the effectiveness of the method.     

An integrated multi-view model evolution framework

A Unified Modeling Language model of a software system can be represented by a sequence of model transformations, starting from an empty model. To effectively support the design of complex systems, transformations help the developer to proceed from an initial requirements model to a platform-specific, executable model. We present a notion of potentially re-orderable model transformations that assist the developer in the design process, and track the semantic dependencies of the different modeling steps. Based on our experience with our own software engineering methodology and modeling tool, we outline a possible implementation that will support developers in revising their model, and still benefit from any subsequent effort that has been spent on model evolution, especially with regard to correctness of the evolving model.     

Matching patterns in strings subject to multi-linear transformations

Suppose we are given two strings of real numbers. The longer string is called text and the other is called pattern. We consider problems within the following framework. Suppose each symbol of the pattern was modified by any transformation which is a member in some family of transformations. Find all occurences of the pattern in the text where the pattern may appear subject to any one of these transformations. Problems are introduced and efficient algorithms are given.     

Gray codes for reflectable languages

We classify a type of language called a reflectable language. We then develop a generic algorithm that can be used to list all strings of length n for any reflectable language in Gray code order. The algorithm generalizes Gray code algorithms developed independently for k-ary strings, restricted growth strings, and k-ary trees, as each of these objects can be represented by a reflectable language. Finally, we apply the algorithm to open meandric systems which can also be represented by a reflectable language.     

汉语文本中特殊符号串的自动识别技术

提出从组成形式和上下文语境两个方面来自动识别汉语文本中的各种特殊符号串。其组成形式用包含约束式的上下文无关文法来描述，改进的LR分析方法进行形式识别；上下文语境采用基于知网概念的特征向量来表达，向量间的欧式距离表示语境间的相似度。实践证明该技术方案是相当有效的。     

纹理图像双特征识别方法

提出了一种能够结合纹理基元形状和大小两种特征的纹理识别方法。该方法首先定义一种编码规则,应用这种规则对图像中纹理基元的轮廓线进行编码,把纹理的表述转化为夹角链码形式。使用后缀数组提取链码中的重复字符串作为特征编码,应用动态规划算法在近似匹配条件下计算特征编码在链码中的重复频率。最后,以特征编码及其重复频率作为目标的形状特征和尺度特征,使用贝叶斯分类方法对纹理进行识别。通过识别实际矿石图片验证了这种方法的有效性。