Shape Decomposition for Graph
Representation
Cai Luyuan, Zhao Meng, Liu Shang, Mao Xiaoyan, and Bai Xiao
Abstract. The problem of shape analysis has played an important role
in the area of image analysis, computer vision and pattern recognition. In
this paper, we present a new method for shape decomposition. The proposed
method is based on a refined morphological shape decomposition process.We
provide two more analysis for morphological shape decomposition. The first
step is scale invariant analysis. We use a scale hierarchy structure to find the
invariant parts in all different scale level. The second step is noise deletion.
We use graph energy analysis to delete the parts which have minor contribution
to the average graph energy. Our methods can solve two problems for
morphological decomposition – scale invariant and noise. The refined decomposed
shape can then be used to construct a graph structure. We experiment
our method on shape analysis.
Keywords: Graph spectra, Image shape analysis, Shape recognition.
1 Introduction
Shape analysis is a fundamental issue in computer vision and pattern recognition.
The importance of shape information relies that it usually contains
perceptual information, and thus can be used for high level vision and recognition
process. There has already many methods for shape analysis. The first
part methods can be described as statistical modeling [4] [12][9] [11]. Here a
well established route to construct a pattern space for the data–shapes is to
Cai Luyuan
School of Computer Science, China University of Geosciences, Wuhan, China
Zhao Meng, Liu Shang, and Bai Xiao
School of Computer Science and Engineering, Beihang University, Beijing, China
Mao Xiaoyan
Beijing Institute of Control Engineering, Beijing, China
Roger Lee (Ed.): SNPD 2010, SCI 295, pp. 1–10, 2010.
springerlink.com c Springer-Verlag Berlin Heidelberg 2010
2 C. Luyuan et al.
use principal components analysis. This commences by encoding the image
data or shape landmarks as a fixed length long vector. The data is then projected
into a low-dimensional space by projecting the long vectors onto the
leading eigenvectors of the sample covariance matrix. This approach has been
proved to be particularly effective, especially for face data and medical images,
and has lead to the development of more sophisticated analysis methods
capable of dealing with quite complex pattern spaces. However, these methods
can’t decompose the shapes into parts and can’t incorporate high level
information from shape. Another problem which may hinder the application
of these method is that the encoded shape vectors must be same length which
need large human interaction pre-processing.
Another popular way to handle the shape information is to extract the
shape skeleton. The idea is to evolve the boundary of an object to a canonical
skeletal form using the reaction-diffusion equation. The skeleton represents
the singularities in the curve evolution, where inward moving boundaries
collide. With the skeleton to hand, then the next step is to devise ways of
using it to characterize the shape of the original object boundary. By labeling
points on the skeleton using so-called shock-labels, the skeletons can then
be abstracted as trees in which the level in the tree is determined by their
time of formation[15, 8]. The later the time of formation, and hence their
proximity to the center of the shape, the higher the shock in the hierarchy.
The shock tree extraction process has been further improved by Torsello and
Hancock[16] recently. The new method allows us to distinguish between the
main skeletal structure and its ligatures which may be the result of local
shape irregularities or noise. Recently, Bai, Latecki and Liu [1] introduced a
new skeleton pruning method based on contour partition. The shape contour
is obtained by Discrete Curve Evolution [10]. The main idea is to remove all
skeleton points whose generating points all lie on the same contour segment.
The extracted shape skeleton by using this method can better reflect the
origin shape structure.
The previous two shape analysis methods, statistical modeling and shape
skeletonization, can be used for shape recognition by combining graph based
methods. For example, Luo, Wilson and Hancock [2] show how to construct
a linear deformable model for graph structure by performing PCA(Principal
Component Analysis) on the vectorised adjacency matrix. The proposed
method delivers convincing pattern spaces for graphs extracted from relatively
simple images. Bai, Wilson and Hancock[18] has further developed
this method by incorporating heat kernel based graph embedding methods.
These method can be used for object clustering, motion tracking and image
matching. For the shape skeleton methods, the common way is to transform
the shape skeleton into a tree representation. The difference between
two shape skeletons can be calculated through the edit distance between two
shock trees[16].
Graph structure is an important data structure since it can be used to represent
the high level vision representation. In our previous work [19], we have
Shape Decomposition for Graph Representation 3.
introduced an image classifier which can be used to classify image object on
different depictions. In that paper, we have introduced an iterative hierarchy
image processing which can decompose the object into meaningful parts and
hence can be used for graph based representation for recognition.
In this paper, we will introduce a new shape decomposition method. Our
method is based on morphological shape decomposition which can decompose
the binary shapes through iterative erosion and dilation process. The
decomposed parts can then be used to construct a graph structure i.e. each
part is a node and the edge relation reflect the relationship between parts,
for graph based shape analysis. However, morphological shape decomposition
has two shortcomings. First, the decomposition is not scale invariant. When
we change the scale level for the same binary shape the decomposition is
different. Second, the decomposed parts contains too much noise or unimportant
parts. When we use graph based methods for shape analysis these
two problems will certainly produce bad influence for our results. Our new
method provide two more analysis for morphological decomposition. We first
solve the scale invariant problem. We decompose the shape through a hierarchy
way. From top to bottom each level representing a different scale size for
the same binary shape from small to big. We decompose each level through
morphological decomposition and then find the corresponding parts through
all levels. We call these parts invariant in all scale levels and use them to
represent the binary shapes. The second step is used to delete the noise parts
which are normally unimportant and small. We construct the graph structure
for the decomposed parts and use graph energy method to analysis the
structure. We find the parts(nodes) which has minor or none contribution to
the average energy for the whole graph structure. The rest parts are kept as
important structure for the shape.
In Section 2, we first review some preliminary shape analysis operations i.e.
the tradition morphological shape decomposition. In Section 3, we describe a
scale invariant shape parts extraction method. In Section 4, we will describe
our graph energy based noise deletion and in Section 5 we provide some
experiment results. Finally, in Section 6, we give conclusion and future work.
Representation
Cai Luyuan, Zhao Meng, Liu Shang, Mao Xiaoyan, and Bai Xiao
Abstract. The problem of shape analysis has played an important role
in the area of image analysis, computer vision and pattern recognition. In
this paper, we present a new method for shape decomposition. The proposed
method is based on a refined morphological shape decomposition process.We
provide two more analysis for morphological shape decomposition. The first
step is scale invariant analysis. We use a scale hierarchy structure to find the
invariant parts in all different scale level. The second step is noise deletion.
We use graph energy analysis to delete the parts which have minor contribution
to the average graph energy. Our methods can solve two problems for
morphological decomposition – scale invariant and noise. The refined decomposed
shape can then be used to construct a graph structure. We experiment
our method on shape analysis.
Keywords: Graph spectra, Image shape analysis, Shape recognition.
1 Introduction
Shape analysis is a fundamental issue in computer vision and pattern recognition.
The importance of shape information relies that it usually contains
perceptual information, and thus can be used for high level vision and recognition
process. There has already many methods for shape analysis. The first
part methods can be described as statistical modeling [4] [12][9] [11]. Here a
well established route to construct a pattern space for the data–shapes is to
Cai Luyuan
School of Computer Science, China University of Geosciences, Wuhan, China
Zhao Meng, Liu Shang, and Bai Xiao
School of Computer Science and Engineering, Beihang University, Beijing, China
Mao Xiaoyan
Beijing Institute of Control Engineering, Beijing, China
Roger Lee (Ed.): SNPD 2010, SCI 295, pp. 1–10, 2010.
springerlink.com c Springer-Verlag Berlin Heidelberg 2010
2 C. Luyuan et al.
use principal components analysis. This commences by encoding the image
data or shape landmarks as a fixed length long vector. The data is then projected
into a low-dimensional space by projecting the long vectors onto the
leading eigenvectors of the sample covariance matrix. This approach has been
proved to be particularly effective, especially for face data and medical images,
and has lead to the development of more sophisticated analysis methods
capable of dealing with quite complex pattern spaces. However, these methods
can’t decompose the shapes into parts and can’t incorporate high level
information from shape. Another problem which may hinder the application
of these method is that the encoded shape vectors must be same length which
need large human interaction pre-processing.
Another popular way to handle the shape information is to extract the
shape skeleton. The idea is to evolve the boundary of an object to a canonical
skeletal form using the reaction-diffusion equation. The skeleton represents
the singularities in the curve evolution, where inward moving boundaries
collide. With the skeleton to hand, then the next step is to devise ways of
using it to characterize the shape of the original object boundary. By labeling
points on the skeleton using so-called shock-labels, the skeletons can then
be abstracted as trees in which the level in the tree is determined by their
time of formation[15, 8]. The later the time of formation, and hence their
proximity to the center of the shape, the higher the shock in the hierarchy.
The shock tree extraction process has been further improved by Torsello and
Hancock[16] recently. The new method allows us to distinguish between the
main skeletal structure and its ligatures which may be the result of local
shape irregularities or noise. Recently, Bai, Latecki and Liu [1] introduced a
new skeleton pruning method based on contour partition. The shape contour
is obtained by Discrete Curve Evolution [10]. The main idea is to remove all
skeleton points whose generating points all lie on the same contour segment.
The extracted shape skeleton by using this method can better reflect the
origin shape structure.
The previous two shape analysis methods, statistical modeling and shape
skeletonization, can be used for shape recognition by combining graph based
methods. For example, Luo, Wilson and Hancock [2] show how to construct
a linear deformable model for graph structure by performing PCA(Principal
Component Analysis) on the vectorised adjacency matrix. The proposed
method delivers convincing pattern spaces for graphs extracted from relatively
simple images. Bai, Wilson and Hancock[18] has further developed
this method by incorporating heat kernel based graph embedding methods.
These method can be used for object clustering, motion tracking and image
matching. For the shape skeleton methods, the common way is to transform
the shape skeleton into a tree representation. The difference between
two shape skeletons can be calculated through the edit distance between two
shock trees[16].
Graph structure is an important data structure since it can be used to represent
the high level vision representation. In our previous work [19], we have
Shape Decomposition for Graph Representation 3.
introduced an image classifier which can be used to classify image object on
different depictions. In that paper, we have introduced an iterative hierarchy
image processing which can decompose the object into meaningful parts and
hence can be used for graph based representation for recognition.
In this paper, we will introduce a new shape decomposition method. Our
method is based on morphological shape decomposition which can decompose
the binary shapes through iterative erosion and dilation process. The
decomposed parts can then be used to construct a graph structure i.e. each
part is a node and the edge relation reflect the relationship between parts,
for graph based shape analysis. However, morphological shape decomposition
has two shortcomings. First, the decomposition is not scale invariant. When
we change the scale level for the same binary shape the decomposition is
different. Second, the decomposed parts contains too much noise or unimportant
parts. When we use graph based methods for shape analysis these
two problems will certainly produce bad influence for our results. Our new
method provide two more analysis for morphological decomposition. We first
solve the scale invariant problem. We decompose the shape through a hierarchy
way. From top to bottom each level representing a different scale size for
the same binary shape from small to big. We decompose each level through
morphological decomposition and then find the corresponding parts through
all levels. We call these parts invariant in all scale levels and use them to
represent the binary shapes. The second step is used to delete the noise parts
which are normally unimportant and small. We construct the graph structure
for the decomposed parts and use graph energy method to analysis the
structure. We find the parts(nodes) which has minor or none contribution to
the average energy for the whole graph structure. The rest parts are kept as
important structure for the shape.
In Section 2, we first review some preliminary shape analysis operations i.e.
the tradition morphological shape decomposition. In Section 3, we describe a
scale invariant shape parts extraction method. In Section 4, we will describe
our graph energy based noise deletion and in Section 5 we provide some
experiment results. Finally, in Section 6, we give conclusion and future work.
No comments:
Post a Comment