4 : Graph Energy Based Noise Deletion

4 : Graph Energy Based Noise Deletion
We continue to use the idea from spectral graph theory [3] to delete the noise
in morphological shape decomposition. Our idea is to use graph Laplacian
energy which reflect the connectiveness and regularity for the graph to delete
the parts(nodes) which has minor or none contribution to the average graph
Shape Decomposition for Graph Representation 7
Laplacian energy per node. The solution is to iteratively delete the parts and
finally stop this process when the average graph Laplacian energy per node
never rise.
We first review the graph Laplacian energy [6]. The Laplacian matrix is
defined as L = D − A, in which D is a degree matrix, and A an adjacency
matrix. Laplacian graph energy has the following standard definition: for a
general graph G = (V,A), with arc weights w(i, j) the Laplacian energy is
E(G) =
|V |

i=1

λi − 2 m
|V |

(8)
In which: the λi are eigenvalues of the Laplacian matrix; m is the sum of
the arc weights over the whole graph, or is half the number of edges in an
unweighted graph; |V | is the number of nodes in graph. Note that 2m/|V |
is just the average (weighted) degree of a node. Now, the Laplacian energy
of a graph can rise or fall; our tests show that this rise and fall is strongly
correlated with the variance in the degree matrix D. This means local minima
tend to occur when the graph is regular.
Since we want to use graph Laplaican energy, we need to first construct
a graph structure for morphological decomposed parts. The graph structure
can be constructed through the method from previous section. We treat each
parts from morphology decomposition as a node in the graph G, the edge
relationship is found through the adjacency and overlap relationship between
each pair of parts.
The process of noise deletion is listed below: 1) We compute the initial
average graph energy for the initial state decomposition E(G)/|N|. 2) For
each iteration, we go through all the nodes in the graph G. For each node
we judge whether we should delete this node. We just compare the previous
average graph energy E(G)/|N| with the average graph energy with this node
deleted E(Gdi)/|N −i|, where Gdi is the graph with ith nodes deleted. If the
the average graph energy E(Gdi)/|N − i| is larger than the previous average
energy then we should delete this node and update the graph structure G.
3) Repeat step two, until E(Gdi)/|N − i| never rise. 4) Output the final
decomposition.
The previous process can detect the nodes which has weak link with rest
nodes in the graph. It will prune the graph structure until it near or reach
regular while keep strong connectiveness within the rest nodes.