Databases Reference
In-Depth Information
tion algorithms that are based on associative memory have higher recognition
accuracy than algorithms that implement recognition using a conventional
memory architecture. Other associative memory algorithms include the Hop-
field network, Kernel Associative Memory (KAM), Morphological Associative
Memory (MAM), and Hamming Associative Memory.
In addition to its associative memory architecture, GN follows some char-
acteristics of graph-based pattern recognition algorithms, as demonstrated in
[47, 48, 49, 50]. However, GN implements in-network processing, and thus
solves the scalability issue encountered in other graph-based pattern recog-
nition algorithms, as described in [51]. According to Nasution [52], the in-
network processing capability of GN offers two advantages: 1) it eliminates the
computational problems encountered in large patterns and pattern databases
and 2) its implementation is ideal for resource-constrained environments, such
as event detection in wireless sensor networks (WSNs).
An overview of graph-based algorithms for pattern recognition is presented
below. Some of their characteristics were inherited by GN.
2.5.1.1
Graph-Based Pattern Recognition
A graph comprises a set of vertices and edges. Therefore, a graph, G, is
represented by G = (V, E), where V is the set of vertices (also known as
nodes or points), E represents the edges (also known as lines or arcs), and
E ⊂ V × V . An edge, e ∈ E, connects two vertices, x, and y ∈ V , and is
denoted by e = (x, y). Graph vertices and edges can contain one or more
pieces of information. If only a single piece of information is available, the
graph is called a labeled graph. If more information is contained on vertices
or edges, the graph is called an attributed graph. Figure 2.8 shows an example
of a labeled graph.
In graph-based pattern recognition, each pattern is represented as a graph.
A modeled (or stored) pattern, P
store
, and an input pattern, P
input
, are repre-
sented by graphs G
store
and G
input
, respectively. As described in [53], pattern
recognition based on a graph representation follows the graph matching prob-
lem: Given G
store
= (V
s
, E
s
) and G
input
= (V
i
, E
i
), where |V
s
| = |V
i
|, a
one-to-one mapping, f : V
i
→ V
s
, exists, such that for any input pattern
element (x, y) ∈ E
i
⇐⇒ (f (x) , f (y)) ∈ E
s
. This mapping function implies
isomorphism, and G
input
is said to be isomorphic to G
store
. This type of
problem is known as exact graph matching. If two graphs have different sets
of attributes or different numbers of vertices or edges, isomorphism does not
occur and an inexact graph matching algorithm is used.
In the field of computer vision, graphs are used to represent images for
the purpose of recognition. In graph-based image recognition, regions of an
image are represented by vertices, and edges are used to signify relationships
between regions. An important issue in graph-based pattern recognition is
that the complexity of the algorithm is significantly affected by an increase
in either the size or quantity of the pattern stored. According to Caetano et
