Wyniki wyszukiwania - BazTech

1

A Descriptive Tolerance Nearness Measure for Performing Graph Comparison

Henry C. J., Awais S. A.

Fundamenta Informaticae

|

2018

|

Vol. 163, nr 4

305--324

EN

This article proposes the tolerance nearness measure (TNM) as a computationally reduced alternative to the graph edit distance (GED) for performing graph comparisons. The TNM is defined within the context of near set theory, where the central idea is that determining similarity between sets of disjoint objects is at once intuitive and practically applicable. The TNM between two graphs is produced using the Bron-Kerbosh maximal clique enumeration algorithm. The result is that the TNM approach is less computationally complex than the bipartite-based GED algorithm. The contribution of this paper is the application of TNM to the problem of quantifying the similarity of disjoint graphs and that the maximal clique enumeration-based TNM produces comparable results to the GED when applied to the problem of content-based image processing, which becomes important as the number of nodes in a graph increases.

2

Metoda poszukiwania strukturalnie niedokładnej odpowiedniości elementów obrazów poprzez poszukiwanie klik optymalnych

Bal A.

Pomiary Automatyka Kontrola

|

2007

|

R. 53, nr 5

9-11

PL

W pracy przedstawiono idee nowych, wykorzystujących informacje o strukturze obrazów, metod poszukiwania niedokładnej odpowiedniości elementów obrazów. W prezentowanych metodach poszukiwanie odpowiedniości elementów obrazów sprowadzono do zadania ustalenia niedokładnej odpowiedniości odpowiednio zdefiniowanych grafów. Na potrzeby rozwiązania tego zadnia opracowano metodę poszukiwania odpowiedniości grafów przez poszukiwanie klik optymalnych. Jako przykład zastosowania prezentowanych metod przedstawiono ich wykorzystanie w zadaniu poszukiwania stereokorespondencji.

EN

In this paper the ideas of novel methods for finding inexact correspondence of image elements, using structural information, are presented. Task of matching image elements is reduced to the problem of inexact graph matching in accordingly defined graphs. For solving this problem method of finding graph matching by optimal clique finding was developed. As an example of practical usage of the described methods, their application in problem of stereomatching is presented.

3

A graph-edit algorithm for hand-drawn graphical document recognition and thier automatic introduction into CAD systems

Lladós J., Martí E.

Machine Graphics and Vision

|

1999

|

Vol. 8, No. 2

195-211

EN

In this work, a graph-based algorithm for symbol recognition in hand-drawn architectural plans has been described. The algorithm belongs to a prototype of man-machine interface consisting in the introduction of hand-drawndesigns to a CADsystem. Documentsand symbol prototypes are represented in terms of a Region Adjecency Graph (RAG) structure. Hence, the localization of symbol instaces in documents is performed by an error-tolerant subgraph isomorphism algorithm that looks for the minimum cost edit sequence that transforms a model graph to an input one. In this paper we describe this algorithm and the set of graph edit operations designed to transform RAGs. The main idea of the algorithm is to formulate the distance between two RAGs in terms of the string edit distance between the boundary strings of the corresponding regions. The main advantage of the algorithm is its ability to cope with distorted structuredand its invariance to rotation, translation and scaling.