检索结果-内蒙古大学图书馆

Speeding up graph edit distance computation through fast bipartite matching

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2011年 6658 LNCS卷 102-111页

作者： Fankhauser, Stefan Riesen, Kaspar Bunke, Horst Institute of Computer Science and Applied Mathematics University of Bern Neubrückstrasse 10 CH-3012 Bern Switzerland

ISBN: (纸本)9783642208430

In the field of structural pattern recognition graphs constitute a very common and powerful way of representing objects. the main drawback of graph representations is that the computation of various graph similarity measures is exponential in the number of involved nodes. Hence, such computations are feasible for rather small graphs only. One of the most flexible graph similarity measures is graph edit distance. In this paper we propose a novel approach for the efficient computation of graph edit distance based on bipartite graph matching by means of the Volgenant-Jonker assignment algorithm. Our proposed algorithm provides only suboptimal edit distances, but runs in polynomial time. the reason for its sub-optimality is that edge information is taken into account only in a limited fashion during the process of finding the optimal node assignment between two graphs. In experiments on diverse graph representations we demonstrate a high speed up of our proposed method over a traditional algorithm for graph edit distance computation and over two other sub-optimal approaches that use the Hungarian and Munkres algorithm. Also, we show that classification accuracy remains nearly unaffected by the suboptimal nature of the algorithm. © 2011 Springer-Verlag Berlin Heidelberg.

关键词： pattern matching

来源：评论

学校读者我要写书评

暂无评论

Hierarchical interactive image segmentation using irregular pyramids

引用

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2011年 6658 LNCS卷 245-254页

作者： Gerstmayer, Michael Haxhimusa, Yll Kropatsch, Walter G. Pattern Recognition and Image Processing Group Institute of Computer Graphics and Algorithms Vienna University of Technology Austria

ISBN: (纸本)9783642208430

In this paper we describe modifications of irregular image segmentation pyramids based on user-interaction. We first build a hierarchy of segmentations by the minimum spanning tree based method, then regions from different (granularity) levels are combined to a final (better) segmentation with user-specified operations guiding the segmentation process. based on these operations the users can produce a final image segmentation that best suits their applications. this work can be used for applications where we need accuracy in image segmentation, in annotating images or creating ground truth among others. © 2011 Springer-Verlag Berlin Heidelberg.

关键词： Image segmentation

来源：评论

学校读者我要写书评

暂无评论

graph-based representations in pattern recognition - 7th IAPR-TC-15 international workshop, GbRPR 2009, Proceedings

Graph-Based Representations in Pattern Recognition - 7th IAP...

引用

7th IAPR-TC-15 international workshop on graph-based representations in pattern recognition, GbRPR 2009

ISBN: (纸本)3642021239

the proceedings contain 37 papers. the topics discussed include: matching hierarchies of deformable shapes;edition within a graph kernel framework for shape recognition;coarse-to-fine matching of shapes using disconnected skeletons by learning class-Specific boundary deformations;an optimization-based approach to mesh smoothing: reformulation and extensions;graph-based analysis of nasopharyngeal carcinoma with Bayesian network learning methods;computing and visualizing a graph-based decomposition for non-manifold shapes;graph-based registration of partial images of city maps using geometric hashing;a polynomial algorithm for submap isomorphism: application to searching patterns in images;a recursive embedding approach to median graph computation;and inexact matching of large and sparse graphs using Laplacian eigenvectors.

关键词：

来源：评论

学校读者我要写书评

暂无评论

A global method for reducing multidimensional size graphs

引用

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2011年 6658 LNCS卷 1-11页

作者： Cerri, Andrea Frosini, Patrizio Kropatsch, Walter G. Landi, Claudia Vienna University of Technology Faculty of Informatics Pattern Recognition and Image Processing Group Austria Università di Bologna ARCES Dipartimento di Matematica Italy Università di Modena e Reggio Emilia Dipartimento di Scienze e Metodi dell'Ingegneria Italy

ISBN: (纸本)9783642208430

this paper introduces the concept of discrete multidimensional size function, a mathematical tool studying the so-called size graphs. these graphs constitutes an ingredient of Size theory, a geometrical/topological approach to shape analysis and comparison. A global method for reducing size graphs is presented, together with a theorem stating that size graphs reduced in such a way preserve all the information in terms of multidimensional size functions. this approach can lead to simplify the effective computation of discrete multidimensional size functions, as shown by examples. © 2011 Springer-Verlag Berlin Heidelberg.

关键词： graphic methods

来源：评论

学校读者我要写书评

暂无评论

Reified literals: A best practice candidate design pattern for increased expressivity in the Intelligence Community

Reified literals: A best practice candidate design pattern f...

引用

5th international Conference on Semantic Technologies for Intelligence, Defense, and Security, STIDS 2010

作者： Peterson, Eric Global Infotek 1920 Association Drive Reston VA 20191 United States

Reifying literals clearly increases expressivity. But reified literals appear to waste memory, slow queries, and complicate graph-based models. We show where this practice can be comparable to unreified literals in these respects and we characterize the cost where it is not. We offer examples of how reification allows literals to participate in a variety of relations enabling a marked increase in expressivity. We begin with a case study in reified person names, and then extend this analysis to reified dates and simple reified scalar values. We show benefits for name matching and temporal analysis such as would be of interest to the Intelligence Community (IC). We then show how these same sorts of analyses can drive or inform any decision as to whether to reify literals.

关键词： Semantics

来源：评论

学校读者我要写书评

暂无评论

Characteristic Polynomial Analysis on Matrix representations of graphs

Characteristic Polynomial Analysis on Matrix Representations...

引用

7th international workshop on graph-based representations in pattern recognition

作者： Ren, Peng Wilson, Richard C. Hancock, Edwin R. Univ York Dept Comp Sci York YO10 5DD N Yorkshire England

ISBN: (纸本)9783642021237

Matrix representations for graphs play an important role in combinatorics. In this paper, we investigate four matrix representations for graphs and carry out an characteristic polynomial analysis upon them. the first two graph matrices are the adjacency matrix and Laplacian matrix. these two matrices call be obtained straightforwardly from graphs. the second two matrix representations, which are newly introduced [9][3], arc closely related with the Ihara zeta function and the discrete time quantum walk. they have a similar form and are established from a transformed graph. i.e. the oriented line graph of the original graph. We make use of the characteristic polynomial coefficients of the four matrices to characterize graphs and construct pattern spaces with a fixed dimensionality. Experimental results indicate that the two matrices in the transformed domain perform better than the two matrices in the original graph domain whereas the matrix associated with the Ihara zeta function is more efficient and effective than the matrix associated with the discrete time quantum walk and the remaining methods.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

Irregular graph Pyramids and Representative Cocycles of Cohomology Generators

Irregular Graph Pyramids and Representative Cocycles of Coho...

引用

7th international workshop on graph-based representations in pattern recognition

作者： Gonzalez-Diaz, Rocio Ion, Adrian Iglesias-Ham, Mabel Kropatsch, Walter G. Univ Seville Dept Appl Math Seville Spain CENATAV Pattern Recognit Dept Havana Cuba Vienna Univ Technol Pattern Recognit & Image Proc Grp A-1040 Vienna Austria

ISBN: (纸本)9783642021237

Structural pattern recognition describes and classifies data based on the relationships of features and parts. Topological invariants, like the Euler number, characterize the structure of objects of any dimension. Cohomology can provide more refined algebraic invariants to a topological space that does homology. It assigns 'quantities' to the chains used in homology to characterize holes of any dimension. graph pyramids can be used to describe subdivisions of the same object at multiple levels of detail. this paper presents cohomology in the context of structural pattern recognition and introduces an algorithm to efficiency compute representative cocycles (the basic elements of cohomology) in 2D using a graph pyramid. Extension to nD and application in the context of pattern recognition are discussed.

关键词： graph pyramids representative cocycles of cohomology generators

来源：评论

学校读者我要写书评

暂无评论

On Computing Canonical Subsets of graph-based Behavioral representations

On Computing Canonical Subsets of Graph-Based Behavioral Rep...

引用

7th international workshop on graph-based representations in pattern recognition

作者： Mankowski, Walter C. Bogunovich, Peter Shokoufandeh, Ali Salvucci, Dario D. Drexel Univ Dept Comp Sci Philadelphia PA 19104 USA

ISBN: (纸本)9783642021237

the collection of behavior protocols is a common practice in human factors research, but the analysis of these large data sets has always been a tedious and time-consuming process. We are interested in automatically finding canonical behaviors: a small subset of behavioral protocols that is most representative of the full data set, providing a view of the data with as few protocols as possible. Behavior protocols often have a natural graph-based representation, yet there has been little work applying graph theory to their study. In this paper we extend our recent algorithm by taking into account the graph topology induced by the paths taken through the space of possible behaviors. We applied this technique to find canonical web-browsing behaviors for computer users. By comparing identified canonical sets to a ground truth determined by expert human coders. we found that this graph-based metric outperforms our previous metric based on edit distance.

关键词： graph theory

来源：评论

学校读者我要写书评

暂无评论

Approximative graph pyramid solution of the E-TSP

引用

IMAGE AND VISION COMPUTING 2009年第7期27卷 887-896页

作者： Haxhimusa, Yll Kropatsch, Walter G. Pizlo, Zygmunt Ion, Adrian Purdue Univ Dept Psychol Sci Coll Liberal Arts Lafayette IN 47907 USA Vienna Univ Technol Fac Informat Inst Comp Aided Automat Pattern Recognit & Image Vienna Austria

the traveling salesman problem (TSP) is difficult to solve for input instances with large number of cities. Instead of finding the solution for an input with a large number of cities, the problem is transformed into a simpler form containing smaller number of cities, which is then solved optimally. graph pyramid solution strategies, using Boruvka's minimum spanning tree step, convert, in a bottom-up processing, a 2D Euclidean TSP problem with a large number of cities into successively smaller problems (graphs) with similar layout and solution, until the number of cities is small enough to seek the optimal solution. Expanding this tour solution in a top-down manner, to the lower levels of the pyramid, leads to an approximate solution. the new model has an adaptive spatial structure and it simulates visual acuity and visual attention. the model solves the TSP problem sequentially, by moving attention from city to city, and the quality of the solutions is similar to the solutions produced by humans. the graph pyramid data structures and processing strategies provide good methods for finding near-optimal solutions for computationally hard problems. Isolating processing used by humans to solve computationally hard problems is of general importance to psychology community and might lead to advances in pattern recognition. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Hierarchical representation graph pyramids Human problem solving Traveling salesman problem Boruvka's minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

Directly computing the generators of image homology using graph pyramids

引用

IMAGE AND VISION COMPUTING 2009年第7期27卷 846-853页

作者： Peltier, Samuel Ion, Adrian Kropatsch, Walter G. Damiand, Guillaume Haxhimusa, Yll Vienna Univ Technol Pattern Recognit & Image Proc Grp Fac Informat A-1040 Vienna Austria Univ Lyon CNRS LIRIS UMR5205 F-69622 Villeurbanne France Purdue Univ Dept Psychol Sci W Lafayette IN 47907 USA

We introduce a method for computing homology groups and their generators of a 2D image, using a hierarchical structure, i.e. irregular graph pyramid. Starting from an image, a hierarchy of the image is built by two operations that preserve homology of each region. Instead of computing homology generators in the base where the number of entities (cells) is large, we first reduce the number of cells by a graph pyramid. then homology generators are computed efficiently on the top level of the pyramid, since the number of cells is small. A top down process is then used to deduce homology generators in any level of the pyramid, including the base level, i.e. the initial image. the produced generators fit on the object boundaries. A unique set of generators called the minimal set, is defined and its computation is discussed. We show that the new method produces valid homology generators and present some experimental results. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Homology generators Irregular graph pyramids

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：