【24h】

Recent Advances in Graph Matching

机译:图匹配的最新进展

获取原文
获取原文并翻译 | 示例
       

摘要

A powerful and universal data structure with applications in various subfields of science and engineering is graphs. In computer vision and image analysis, graphs are often used for the representation of structured objects. For example, if the problem is to recognize instances of known objects in an image, then often models, or prototypes, of the known objects are represented by means of graphs and stored in a database. The unknown objects in the input image are extracted by means of suitable preprocessing and segmentation algorithms, and represented by graphs that are analogous to the model graphs. Thus, the problem of object recognition is transformed into a graph matching problem. In this paper, it is assumed that there is an input graph that is given on-line, and a number of model, or prototype, graphs that are known a priori. We present a new approach to subgraph isomorphism detection which is based on a compact representation of the model graphs that is computed off-line. Subgraphs that appear multiple times within the same or within different model graphs are represented only once, thus reducing the computational effort to detect them in an input graph. In the extreme case where all model graphs are highly similar, the run time of the new algorithm becomes independent of the number of model graphs. We also describe an extension of this method to error-correcting graph matching. Furthermore, an approach to subgraph isomorphism detection based on decision trees is proposed. A decision tree is generated from the models in an off-line phase. This decision tree can be used for subgraph isomorphism detection. The time needed for decision tree traversal is only polynomial in terms of the number of nodes of the input graph. Moreover, the time complexity of the decision tree traversal is completely independent on the number of model graphs, regardless of their similarity. However, the size of the decision tree is exponential in the number of nodes of the models. To cut down the space complexity of the decision tree, some pruning strategies are discussed.
机译:图形是一种强大而通用的数据结构,在科学和工程学的各个子领域都有应用。在计算机视觉和图像分析中,图形通常用于表示结构化对象。例如,如果问题在于识别图像中已知对象的实例,则通常通过图形表示已知对象的模型或原型,并将其存储在数据库中。输入图像中的未知对象通过适当的预处理和分割算法提取,并由类似于模型图的图表示。因此,将对象识别问题转化为图匹配问题。在本文中,假设有一个在线给出的输入图,以及许多先验已知的模型或原型图。我们提出了一种新的子图同构检测方法,该方法基于离线计算的模型图的紧凑表示。在相同或不同模型图中多次出现的子图只表示一次,因此减少了在输入图中检测到它们的计算量。在所有模型图都非常相似的极端情况下,新算法的运行时间变得与模型图的数量无关。我们还描述了此方法的扩展,用于纠错图形匹配。此外,提出了一种基于决策树的子图同构检测方法。在离线阶段从模型中生成决策树。该决策树可用于子图同构检测。就输入图的节点数而言,决策树遍历所需的时间仅是多项式。此外,决策树遍历的时间复杂度完全与模型图的数量无关,而与它们的相似性无关。但是,决策树的大小在模型的节点数上是指数级的。为了降低决策树的空间复杂度,讨论了一些修剪策略。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号