Information Technology Reference
In-Depth Information
If
A
=
C
t
C
,as
C
t
is not full ranked (sum of rows is equal to zero), the
determinant of
A
is zero. Furthermore, let
z
=
Cy
,thenhave
y
t
C
t
Cy
=
z
t
z>
=0
and hence
A
is positive semi-definite. The matrix
A
matrix is usually sparse for
large problems, with the diagonal elements
a
ij
= number of edges incidents to
vertex
i
; and the off-diagonal elements:
a
ij
=
−
1 if an edge exists between vertices i and j
0otherwise
(2)
In the literature, this matrix is referred to as the Laplacian matrix (also called
topological or graph Laplacian), it plays a central role in various applications.
If
A
=
,where
.
is the elementwise matrix multiplication operator (or
Hadamard-Schur product) and
|
A.Ψ
|
⎛
⎝
⎞
⎠
01
1
10 1
10 1
Ψ
=
(3)
.
.
.
.
.
.
.
.
.
1
A
is commonly known as the adjacency matrix of the graph.
2.2
N
th
Order Node-Edge Matrix
C
as defined below represents the first order connectivity of the image. In many
cases, it might also be useful to define an extended node-edge matrix taking into
account ”weak” connection between nodes. For example, we might be interested
to define a ”weak” connection between second order neighbouring nodes.
C
can
be then defined by:
⎡
⎤
C
1
.
C
N
⎣
⎦
C
1
..N
=
(4)
where
C
1
represents the connection (between first order neighbours) and
C
N
represents the connection (between
N
t
h
order neighbours).
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
t
C
1
.
C
N
C
1
.
C
N
=
C
1
C
1
+
+
C
t
N
C
N
A
=
C
1
..N
C
1
..N
=
.
···
(5)
Like in the definition of the node-edge matrix, the coecients of
C
k
are either
equals to 0,
c
k
or
c
k
.The
c
k
coecients are strictly positive and have to verify
the following properties:
−
1
c
k
c
k
≥
≥
(6)
c
k
+1
Search WWH ::
Custom Search