# Re: Fuzzy graph isomorphism

Benoit Debaque (bdebaque@cybercable.fr)
Sun, 22 Aug 1999 14:27:21 +0200 (MET DST)

Thank you William for your reply, your questions permit me to get a clearer
view of my problem.

First, I constructed an andjacency graph between the extracted segments of
an image, each node represents a segment and arcs represent relations
between them, for example one of the relations describe the normalized
angles between adjacent segments, therefore the labels attributed to the
adjacency graphs are fuzzy in the sense that the relative angles values are
vague due to the image acquisition & extraction process. Membership
functions are described for certain angles intervals. There is others
attributes such as distance, segment length, etc. each of one describing a
unary fuzzy relation between discrete sets. This is how the "fuzzy data
graphs" are constructed.

Furthermore, given an approximated viewpoint of a projected CAD model of the
object of interest, a description of the relations of the segments is given
in an adjacency attributed graph in a similar manner aforementioned ,
finally "fuzzy model graphs" are constructed.

I think of matching those two graphs so to recognize certain common
structures. I thought of using isomorphism with error correction, i.e. using
cost functions to permits overdetected features to be taken into account
during the recognition process, the best matched features will be revealed
with the match having the minimal cost function.

My problem is more like describing those cost functions, knowing that the
following possibilities are available:
- delete a vertex
- delete an edge
- insert an edge
- label a vertex
- label an edge

since my graphs are not binary but rather discrete numbers comprised between
[0,1], it would be clever to use fuzzy operations (similarity measure) as
cost functions.....

I hope this gave you a better understanding.

Benoit

----- Original Message -----
From: WSiler <wsiler@aol.com>
Newsgroups: comp.ai.fuzzy
To: <bdebaque@cybercable.fr>
Sent: Saturday, August 21, 1999 4:41 PM
Subject: Re: Fuzzy graph isomorphism

> >I am currently working on structural pattern recognition, and I made an
> >adjacency graph description of both features coming from the data and
the
> >model. The attributes of my graphs are labeled in a Fuzzy way, therefore
I
> >want to match those two graphs to obtain evidences of common structures.
> >
> >Did anyone heard about fuzzy graph isomorphism before ?
>
> It is not clear to me what you mean by "The attributes of my graphs are
labeled
> in a Fuzzy way". Does this mean that you have a discrete fuzzy set of
> attributes, and that with each attribute is associated a grade of
membership
> representing the extent to which that attribute is characteristic of
"model" or
> "data"? Where do the nodes of the graph fit in here?
>
> You also mention an "adjacency graph description of both features coming
from
> the data and the model". Is this a fuzzy set of attributes, whose grades
of
> membership represent the extent to which an attribute is similar in the
"model"
> and "data"?
>
> If you can supply a more complete description of your problem, perhaps I
can
> help you. There are several measures of similarity between fuzzy sets, but
> there are problems in selecting which to use, and which logical fuzzy
operators
> to use.
>
> William Siler
>
>
>

############################################################################
This message was posted through the fuzzy mailing list.
(1) To subscribe to this mailing list, send a message body of
"SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at
(2) To unsubscribe from this mailing list, send a message body of
"UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com"
to listproc@dbai.tuwien.ac.at
(3) To reach the human who maintains the list, send mail to
fuzzy-owner@dbai.tuwien.ac.at
(4) WWW access and other information on Fuzzy Sets and Logic see
http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info
(5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html