标志树文法及其语法分析

树文法是一种高维文法，能够用来表达二维以上复杂对象的构造规则．在模式识别、图式语言等领域有着广泛的应用前景．本文在树文法有关概念基础上提出了标志树、连接标志、标志树文法等概念，构造了标志树的匹配和识别算法，并成功解决了标志树文法的语法分析器构造问题．     

手写印刷体汉字识别方法2-D EAG

本文介绍手写印刷体汉字识别方法2-D EAG。主要的工作为:提出了二维扩展属性文法模式识别方法,可实现自底向上归约和自顶向下推导双向信息传递和控制;提出了一种直接利用二维信息进行识别的方式,可避免特征线性化造成的信息丢失;提出了多义文法、共生文法和结构推断三种在文法之间建立联系,利用结构类比区分极相似字的 识别算法;提出了多冗余归约机制,双边缘弹性跟踪笔段抽取算法,多冗余有引导部件抽取算法。用2-D EAG方法对100字种实际手写汉字进行了识别实验,在识别大畸变汉字(包括部分连笔字)方面得到了很好的结果。     

场景关系图学习的群组行为识别

为解决群组行为识别中复杂个体关系描述不准确，造成的个体关系推理不可靠的问题，关注于面向个体、群体、场景三个方面来构建场景关系图，提出场景关系图网络用于实现群组行为识别。该网络包括特征提取模块、场景关系图推理模块以及分类模块。特征提取模块通过卷积神经网络提取个体特征、群组特征、和场景特征。为了充分描述场景对于个体和群组描述的影响，场景关系图推理模块通过使用两分支网络分别建立个体—场景关系图以及群组—场景关系图帮助学习个体特征和群组特征。场景关系图推理同时考虑了个体特征对群组特征的影响，并引入了跨分支关系。分类模块用于将个体特征和群体特征进行分类预测。实验结果显示该方法在volleyball和collective activity数据集上的群组识别准确率分别提升了1.1%和0.5%,证实了提出的场景关系图在描述个体特征和群组特征上的有效性。     

vCGG:一种基于虚结点的空间图文法形式框架

作为一种二维的形式化方法,图文法为可视化语言提供了直观而规范的描述手段.然而,大多数图文法形式框架在空间语义处理能力方面有所不足,影响了图文法的表达能力及其实际应用范围.针对现存的问题,构建了一种新型空间图文法形式框架vCGG （virtual-node based coordinate graph grammar）.区别于其他空间图文法,vCGG在产生式中通过定义虚结点的概念描述产生式与主图之间的语法结构与空间语义关系,在保留抽象能力的同时,提高了其空间语义配置性能.通过与几种典型空间图文法框架比较,vCGG形式框架在直观性、规范性、表达能力以及分析效率方面均有着较好的表现.     

包装盒型的三维仿真研究

提出了一种基于盒型拓扑图的对二维包装平面图进行三维仿真的方法,对经过预处理的二维数据进行拓扑分析,采用盒型拓扑图描述分析结果,能够识别和处理带有开窗的复杂盒型,最后采用折叠传播算法构造三维模型．     

一种基于图匹配的复杂草图识别方法

复杂草图识别是手绘草图输入中的一个困难任务。现存的草图识别方法强调的是图形对象简单．但这不适合具有不同复杂性的复杂草图的识别。本文对具有不同复杂性的复杂图形对象提出一个基于图形的统一表示法，文中根据不同信息枉度将复杂图形分别转化为空间关系图(SRG)。文中提出了一个约束的部分枚举．以减小识别复杂草图时匹配SRG的状态空间。实验结果显示．我们的方法可适用于具有不同复杂度的各种复杂图形对象的识别。     

上下文相关图文法的表达能力分析

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.     

On the Expressiveness of Context-Sensitive Graph Grammars

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.     

属性文法中变元间的关系

本文从模式的语义、句法描述着眼,分析了一个属性文法的产生式变元间的几种关系,把 这些关系作为语义部分的内容,从而推广了属性文法,以推广后的属性文法为基础,引入控制 连接图作为主要的限制条件,提出一种"语义程序文法",并把标准模式与畸变模式之间的联系 用限制条件描述.最后利用变元间的关系,把模式的描述与知识的表达联系起来.     

用于手写汉字识别的二维扩展属性文法中的文法归约

本文介绍用于识别手写印刷体汉字的二维扩展属性文法方法中文法归约阶段的工作。从四方位取出部件之后,按照部件组合属性和部件框位置关系对部件进行归约。由于利用了汉字部件组合关系中的信息冗余及扩展属性文法的语义处理能力,这种方法降低了对部件正确抽取的要求,但仍能识别畸变较大的汉字,并能有效地区分极相似字。     

A neural network approach to CSG-based 3-D object recognition

Describes the recognition subsystem of a computer vision system based on constructive solid geometry (CSG) representation scheme. Instead of using the conventional CSG trees to represent objects, the proposed system uses an equivalent representation scheme-precedence graphs-for object representation. Each node in the graph represents a primitive volume and each are between two nodes represents the relation between them. Object recognition is achieved by matching the scene precedence graph to the model precedence graph. A constraint satisfaction network is proposed to implement the matching process. The energy function associated with the network is used to enforce the matching constraints including match validity, primitive similarity, precedence graph preservation, and geometric structure preservation. The energy level is at its minimum only when the optimal match is reached. Experimental results on several range images are presented to demonstrate the proposed approach     

A graph grammar programming style for recognition of music notation

Graph grammars are a promising tool for solving picture processing problems. However, the application of graph grammars to diagram recognition has been limited to rather simple analysis of local symbol configurations. This paper introduces the Build-Weed-Incorporate programming style for graph grammars and shows its application in determining the meaning of complex diagrams, where the interaction among physically distant symbols is semantically important. Diagram recognition can be divided into two stages: symbol recognition and high-level recognition. Symbol recognition has been studied extensively in the literature. In this work we assume the existence of a symbol recognizer and use a graph grammar to assemble the diagram's information content from the symbols and their spatial relationships. The Build-Weed-Incorporate approach is demonstrated by a detailed discussion of a graph grammar for high-level recognition of music notation. See Appendix A for an illustration of the terms for musical symbols used in this paper.     

A stochastic graph grammar for compositional object representation and recognition

This paper illustrates a hierarchical generative model for representing and recognizing compositional object categories with large intra-category variance. In this model, objects are broken into their constituent parts and the variability of configurations and relationships between these parts are modeled by stochastic attribute graph grammars, which are embedded in an And-Or graph for each compositional object category. It combines the power of a stochastic context free grammar (SCFG) to express the variability of part configurations, and a Markov random field (MRF) to represent the pictorial spatial relationships between these parts. As a generative model, different object instances of a category can be realized as a traversal through the And-Or graph to arrive at a valid configuration (like a valid sentence in language, by analogy). The inference/recognition procedure is intimately tied to the structure of the model and follows a probabilistic formulation consisting of bottom-up detection steps for the parts, which in turn recursively activate the grammar rules for top-down verification and searches for missing parts. We present experiments comparing our results to state of art methods and demonstrate the potential of our proposed framework on compositional objects with cluttered backgrounds using training and testing data from the public Lotus Hill and Caltech datasets.     

A grammatical approach to self-organizing robotic systems

In this paper, we define a class of graph grammars that can be used to model and direct concurrent robotic self-assembly and similar self-organizing processes. We give several detailed examples of the formalism and then focus on the problem of synthesizing a grammar so that it generates a given, prespecified assembly. In particular, to generate an acyclic graph we synthesize a binary grammar (rules involve at most two parts), and for a general graph we synthesize a ternary grammar (rules involve at most three parts). In both cases, we characterize the number of concurrent steps required to achieve the assembly. We also show a general result that implies that no binary grammar can generate a unique stable assembly. We conclude the paper with a discussion of how graph grammars can be used to direct the self-assembly of robotic parts.     

基于面向对象信任攻击图的信任风险传播模型

针对信任环境系统中存在的信任攻击问题,设计基于面向对象的信任攻击图模型。利用Take规则、Grant规则和Pervade规则,描述信任主体对象属性弱点导致的信任级别的提升、信任关系的传递、渗透与扩散问题,使攻击可达距离更大。根据弱点利用规则和信任关系盗用规则,提出多项式时间复杂度信任关系传递闭包生成算法及基于信任关系传递闭包的信任风险传播算法。实验结果证明了该模型的正确性。     

含假结RNA二级结构类的图语法

用最小自由能法预测RNA二级结构是NP困难问题,其根本原因是假结的存在。近几年的预测算法都针具有一定结构特征的假结寻找多项式时间算法进行预测。论文针对RNA二级结构图提出一种图语法,该语法由初始结构图集和重写规则集构成,用重写规则在初始结构图上的不断重写得到的结构图都是该语法的语言。分析了5个主流RNA二级结构预测算法的目标集,给出它们的图语法,使得目标集的结构特征一目了然,目标集间的真包含关系也通过图语法直观地体现出来。     

A class of linearly parsable graph grammars

Summary Specializing an existing graph grammar model we look in detail at node context-free graph grammars. With a slight generalization the parse trees for context-free Chomsky grammars can be used to describe derivations of these graph grammars.As shown already in former works the precedence graph grammars are defined as a subclass of context-free graph grammars by certain algebraic restrictions on the form of the rules. Then we can prove that every precedence grammar is unambiguous and additionally the reduction process in such a grammar read as replacement system is finite.The most important aim in defining the predence relations was a simple parsing method. This is realized because it is shown that the syntactic analysis for precedence graph grammars can be done in a time which linearly depends on the size of the input graph.The whole method has been implemented and a documentation is available.     

A music notation construction engine for optical music recognition

Optical music recognition (OMR) systems are used to convert music scanned from paper into a format suitable for playing or editing on a computer. These systems generally have two phases: recognizing the graphical symbols (such as note‐heads and lines) and determining the musical meaning and relationships of the symbols (such as the pitch and rhythm of the notes). In this paper we explore the second phase and give a two‐step approach that admits an economical representation of the parsing rules for the system. The approach is flexible and allows the system to be extended to new notations with little effort—the current system can parse common music notation, Sacred Harp notation and plainsong. It is based on a string grammar and a customizable graph that specifies relationships between musical objects. We observe that this graph can be related to printing as well as recognizing music notation, bringing the opportunity for cross‐fertilization between the two areas of research. Copyright © 2003 John Wiley & Sons, Ltd.