 Open Access
 Total Downloads : 14
 Authors : Kaixiang Wang
 Paper ID : IJERTV7IS060169
 Volume & Issue : Volume 07, Issue 06 (June 2018)
 Published (First Online): 20062018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Image Segmentation with Multiple Hypergraph Fusion and Superpixels
Kaixiang Wang
School of Computer Science and Technology, Nanjing Normal University,
Nanjing 210046, China
Abstract. – This paper presents a new method of image segmentation based on superpixels and multiple hypergraph fusion. In this paper, the original image is oversegmented by the ultrapixel segmentation algorithm SLIC, and the superpixel blocks are extracted from the two aspects of color information and gradient information. A hypergraph model is constructed for each channel of the features. From the respect of random walk, the information of multiple hypergraphs is fused to construct the multihypergraph laplacian matrix. After obtaining the multihypergarph laplacian matrix, we construct the optimization model and solve the model by crossing the iterations. Then we can get the results of the superpixel blocks and the image segmentation results. With the superpixels and multiple hypergarph fusion, our method can reduce the loss of information effectively and make the segmentation more precise. Our method was evaluated in Berkeley Segmentation Database. The comparative experiments result with some stateoftheart segmentation algorithms show that our method can give better segmentations for the natural images.
Keywords: Image Segmentation, MultiHypergraph, Superpixels, Spectral Clustering

INTRODUCTION
With the development of information technology, image technology plays an increasingly important role in artificial intelligence, target recognition and tracking, medical imaging and other fields. Image technology consists of three parts, image processing, image analysis and image recognition, the image processing stage is the basis and key to the following applications. The image segmenta tion as an important step in the image processing stage is the focus of research on the whole image field. Therefore, image segmen tation technology has become a very important and difficult research topic in pattern recognition, artificial intelligence and computer vision [25].
Image segmentation is the process of partitioning an image into objects and their backgrounds [26]. Image segmentation based on graph theory and hypergraph has always played an important role in image segmentation [3]. The theory of mathematic provides theoretical support for its development. The theory of graph provides a unified framework for any image. The structure of graph theory is very suitable for image segmentation, and the idea of image segmentation based on graph theory shows a good development prospect.
A graphbased representation can only represente binary relations between vertices, but we may need to represent a higher order relationship in many situations. An extension is provided by hypergraphs [27], which is a generalization of a graph, as the underlying model for the image content. The edges of hypergraphs called hyperedges, each hyperedge is a subset of the set of vertices. As an image modeling tool, compared to standard graphs that model pairs of pixels as their edges, hypergraphs can model image patches as their hyperedges. By the means of hyperedges, higherorder relations between nodes can be directly modeled in a hypergraph [5].
The traditional structure of the graphbased segmentation algorithm is based on the pixels. With the size of image increasing, the scale of the graph increasing accordingly. If the superpixels are used instead of the pixels, the scale of the graph and the computa tional complexity can be greatly reduced. The superpixel is a set of pixels in the image that are consistent and capable of expressing the local structural features of images. The number of super pixels is much smaller than the number of pixels in the image, this will help to reduce the computational complexity of subsequent processing. The superpixel also has some ability of local structural feature expression, which is beneficial to the extraction and expression of local features.
Although segmentation algorithm based on graph theory has been widely applied, it still has some limitations. In this paper, we proposed a new strategy for image segmentation method based on superpixels and multiple hypergraph fusion, namely Multiple Hypergraph Fusion Segmentation(MHFS). Algorithm flowchart is show in Figure 1. Compared with the current graphbased seg mentation algorithm, the proposed MHFS has the following contributions: Firstly, the normal graph can only depict the binary relation between objects, but the hypergraph structure we use can depict higherorder relationships; the hypergraph structure can express higherorder relationships between superpixels better and improve the accuracy and validity of the model. Secondly, we construct different hypergraphs based on different features, then we fused the hypergraphs through constructing a fusion laplacian matrix and fusing the hypergraphs in the view of random walk. This step reduces the loss of information effectively and makes the segmentation more precise. Thirdly, we use segmentation method based on superpixels for image segmentation, which effectively reduces the size of the graph model and the improves the efficiency of the algorithm.
The rest of this paper is organized as follows: The proposed image segmentation algorithm is introduced in section 2. In section 3, we evaluated our methods and compare with some state of art methods. Conclusions are discussed in section 4.

APPROACH
In this chapter, we will detail our proposed algorithm. We introduce some basic notions on hypergraphs before the main steps of our approach. The first step of our approach is to generate superpixels and extract the features. Our second step is to construct hypergraphs based on different features. Then we construct the Multihypergraph laplacian matrix. Finally, we conduct the multi hypergraph spectral clustering to get the final result of segmentation.

Preliminary
Let V denote a finite set of samples, and let E be a family of subsets e of V such that = V. G = (V, E) is then called a hyper graph with the vertex set V and the hyperedge set E. A hyperedge which contains just two vertices is just a simple graph edge. A weighted hypergraph is a hypergraph that has a positive number (e) associated with each hyperedge e, called the weight of hy peredge e. We denote a weighted hypergraph by G = (V, E, ). A hyperedge e is said to be incident with a vertex v when v V. The degree of each vertex v V is defined as:
() = ()
{}
(1)
We let  denote the cardinality of a given arbitrary S. The degree of a hypergraph e E is defined to as:
(e) =  (2)
A hypergraph G can be represented by a  Ã—  matrix H with entries h(v, e) = 1, if v e and 0 otherwise, called the incidence matrix of G. Based on matrix H, the degree of each vertex and each hyperedge can be calculated as:
d(v) = ()(, )
(e) = (, )
(3)
(4)
Let and denote the diagonal matrices containing the vertex and hyperedge degrees respectively, and let W denote the diagonal matrix containing the weights of hyperedges. Then the adjacency matrix A of hypergraph G is defined as:
A = HW (5)
where is the transpose of H.[6]

Superpixels generation and feature extraction
In this paper, we adopt the simple linear iterative clustering (SLIC) [17] to over segmentation the image. We can get compact, nearly uniform ultrapixel because SLIC has several advantages: 1) the generated super pixels as cells are usuallycompact and neat, from which neighborhood features are easier to express. 2) It can not only work on the color map, but also be compatible with grayscale.
3) It needs to set very few parameters, i.e., only the preset number of ultrapixel. 4) compared to other ultrapixel segmentation method, SLIC has advantages in the running speed, bringing ultrapixel compactness and good contour retention.
When the superpixels are extracted, we can handle the image segmentation by the superpixels, which reduces the computing com plexity greatly. In our methods, we employ two kinds of features commonly used in image segmentation: color and gradient infor mation. Each of these two kinds of features has three channels. In our method, we will hypergraph for each channel, resulting in six hypergraphs. In the following, before we introduce how to construct hypergraphs, we show how to extract these two kind of features.
The RGB color space is widely used in image segmentation. Actually, it also has the simplest formulation and explanation. RGB color space to red, green and blue based on the three basic colors, to varying degrees of superposition, resulting in a rich and wide range of colors, so commonly known as three primary colors mode. The histogram of color often constructed on images, now we apply it to superpixels. For a color image, each superpixels has three channels. For each superpixel, we will generate three histograms according to three channels.
Besides the color features, gradient features can help to perform segmentation too. Histogram of oriented gradient based on super pixels is derived from the HOG characteristics,[24] we repute a superpixel here as a cell in the HOG, the superpixel block is irregular so we cannot get a block consist of several cells. Here we just use HOG to describe the cell direction gradient information to describe the superpixel gradient information. For each super pixel block, we can get a vector representing the gradient information on each of the three channels.
Thus we have six vectors to describe the image features, and then we will create a supermap for each of the six features, respectively, from the perspective of the six features to describe the highorder relationship between the ultrapixels.

Hypergraph construction
The INH (Image Neighborhood Hypergraph) model[5][8] has been found very effective at representing the image content. In this paper, we use the superpixels based INH to construct hypergraphs.
A hypergraph is a pair H = (X, E), where X = 1, 2, , is the set of superpixels and E = 1, 2, , is the set of hyperedges. The image will be represented by the following mapping:
I X 2 (6)
Vertices of X are called superpixels, elements of C are called features. Let d be a distance onX, it deflnes the distance on space. Let
be a distance on C, it describes the distance on feature.
Different from the original INH model, we conduct the model on superpixels and we use the mean of space location of pixels in a superpixel to represent the space location of the superpixel. The features of superpixels are constructed in section 3.1.
We have a neighborhood relation on an image defined by:
x X, ,(x) = { X, x((), ()) < (, ) } (7)
The neighborhood of x on the grid will be denoted by ,(x). To each image I, we can associate a hypergraph:
, (I) = (X, (x, (x))) (8)

Multihypergraph laplacian matrix construction
From the above, we can build an image superpixel hypergraph structure for each feature. Then we develop a method to combine the information of the hypergraphs. Specifically, we associate each hypergraph with a natural random walk.[15] Then the transition probabilities and stationary distribution of the hypergraphs are fused.
Let P denote the transition probability matrix of this hypergraph random walk. Then each entry of P is:
(, ) (, )
p(u, v) = ()
The stationary distribution of the random walk is:
()
()
()
(9)
(v) = () (10)
Then we can explain the multiple hypergraph cut in terms of a random walk[16]:
() = 1()
(11)
1 1() + (1 )2()
() = (1 )2()
(12)
2 1() + (1 )2()
The parameter is used to specify the relative importance of each graph in clustering. Then new transition probabilities among
vertices are defined as:
p(u, v) = 1()1(, ) + 2()2(, ) (13)
Then we can get the stationary distribution from a straightforward computation.
(v) = 1() + (1 )2() (14)
The above fusion is conduct on two hypergraphs, but we may have more than two hypergraphs to fuse in many time. In this paper,
we have six hypergraphs to fuse for each image, so we need extend this algorithm and make it enable to fuse any numbers of hypergraphs.
We extend the number of graphs from two to N and transfer the equation to matrix notation:
P = 1
=1
(15)
=
=1
(16)
Please be noted that, as shown, the transition probability matrix and stationary distribution matrix of the fused hypergraph are. not simply linear combinations on the laplacian matrix of each hypergraph.
Then we can get the laplacian matrix of the fused hypergraph as follows:
+
L =

Multihypergraph spectral clustering
2 = ( )
=1
(17)
Different machine learning tasks can be conducted on hypergraphs. The spectral clustering framework can be formulated as:
. . =
min
Ã—
(1212) (18)
where X Ã— is a matrix consisting of the column vectors and k is the number of clusters. The column vectors of X are indeed the eigenvectors corresponding to the k smallest eigenvalues obtained from the eigendecomposition (EVD) on 1212. After row normalization of these eigenvectors, we can apply any classical clustering algorithm such as kmeans to partition these low dimensional embeddings.[12]
As mentioned in section 3.3, the multihypergraph laplacian matrix has been contracted. Then, the multiple hypergraph fusion based spectral clustering can be formulated as:
min
Ã—,
( ( ( )) ) + 2 (19)
=1
s. t. = 1 , > 0, = 1, ,
=1
=
The regularization term 2 is adopted to avoid the fastening on one manifold, and is the tradeoff parameter to control the contribution of regularization term 2.[9][13][14]
The optimization problem can be solved by cross iteration. For a fixed , Eq.(19) can be simplified to:
min
Ã—,
( ( ( )) ) + 2 (20)
=1
where M =
. . =
=1
. The column vectors of X are indeed the eigenvectors corresponding to the k smallest eigenvalues obtained
from the eigendecomposition (EVD) on M. For a fixed X, Eq.(19) can be simplified to:
min
Ã—,
( ) + 2 (21)
=1
. . = 1
=1
Where = (). The solution can be obtained as followed:
() () + 2
= =1
2
(22)
We can get the X Ã— after the cross iterations above, X Ã— is a matrix consisting of the column vectors. After row normal ization of these eigenvectors, we can apply any classical clustering algorithm such as kmeans to partition these lowdimensional embeddings. Then the superpixels of the image will be divided to k parts.


EXPERIMENTS
In this section, the proposed MHFS (multiple hypergraph fusion segmentation) is extensively evaluated on the Berkeley Segmenta tion Database in comparison with the state of the art. We follow [10] to use the Berkeley Segmentaion Dataset as the experimental data support. BSDS500 database includes 500 images and the corresponding ground truth data (each image has at least 4 human annotations), we choose 30 color images randomly from the BSDS500.
In this part of the experiment, we selected the Mean Shift[7], SAS[4], GLgraph[10] three image segmentation methods and our methods for comparative experiments. All results are compared to the human segmented segmentation results. In order to quantita tively compare the difference in performance of four algorithms, we introduce precision for regions, recall for regions, Fscore for regions, IOU, error. Precision, recall, IOU, Fscore values between 0 and 1, and the value gets closer to 1 means a better performance. Error also values between 0 and 1, and the values gets closer to 0 means a better performance.
Fig. 2. Comparison of our method with stateofart methods over the Berkeley segmentation database.
Figure 2 shows segmentation results of Meanshift, SAS, GLgraph and the proposed method. (a) shows the original image, (b) shows the results of MS, (c) shows the results of SAS, (d) shows the results of GLgraph, (e) is obtained with our method, and (f) is the groundtruth.
Table 1 records the results of segmentation precision for regions, recall for regions, Fscore, IOU, error for the four algorithms. It is also the comparisons of our method(MHFS) with stateofart methods over the Berkeley segmentation database.
Through the above numerical experiments, we can see that the proposed segmentation algorithm outperforms the Normalized Cut segmentation algorithm, the SAS segmentation algorithm, the GLgraph segmentation algorithm with performance and efficiency. From the experimental results, we can clearly find that the segmentation method we proposed can better deal with the edge of t he image segmentation problem. Such as the first picture, there is a plane in the sky while the plane appearance similar color and the color of the sky, but we can segment them perfectly. The reason of performance is that the hypergraph structure can describe higher order relationships, so it is very suitable to deal with edge problem. The GLgraph is based on the common graph model. The second order relationship of ordinary graph is difficult to depict the complex relationship between superpixels.
Table 1: Comparison of our method with stateofart methods over the Berkeley segmentation database
Methods
Precision
Recall
Fscore
IOU
error
MS
94.04
92.63
93.04
87.35
4.74
SAS
93.52
96.23
94.65
90.29
3.25
GLgraph
91.79
96.10
93.58
88.30
4.49
MHFS
96.60
94.97
95.37
91.40
2.68
Both in SAS and GL graph, there is only a graph/hypergraph constructed to describe the relationships among pixels/superpixels. For different characteristics, the relationship between the pixel block is different, there must be loss of information if we only use a hypergraph to represent the image. With the help of multiple hypergraphs based on different characteristics, we can describe high order relationships well and effectively reduce the loss of information, so the segmentation results are better.

CONCLUSION
This paper presents an image segmentation method based on superpixels and multiple hypergraph fusion. The method mainly im proves the efficiency and precision of the image segmentation from the following aspects: We use segmentation method based on superpixels to reduces the size of the graph model and the improves the efficiency of the algorithm. The hypergraph structure which we used expresses the higherorder relationships can express the relationships between superpixels well. The most important is that we construct hypergraphs on each feature and fuse the hypergraphs through constructing a fusion laplacian matrix in the view of random walk. The successful fusion of different features reduces the loss of information effectively and makes the segmentation more precise.
The proposed method has some defects need to deal with: (1) the description of the superpixel features exist certain difficulties, some traditional image feature descriptors based on pixels are difficult to directly applied to superpixels. (2) the relationship between vertexes and hyperedges in hypergraph structure is binary (0 or 1), which belongs to hard segmentation; In some cases such as the images has blurred boundary, the soft segmentation based on probability is more suitable.
REFERENCES

Liu J, Wang C, Danilevsky M, et al. Largescale spectral clustering on graphs[C]// International Joint Conference on Artificial Intelligence. AAAI Press, 2013:14861492.

A.Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems 14, Cambridge, MA, 2002. MIT Press

Shi J, Malik J. Normalized Cuts and Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 22(8):888905

Li Z, XiaoMing Wu, Chang S F. Segmentation using superpixels: A bipartite graph partitioning approach[C]// IEEE Conference on Computer Vision and Pattern Recognition. IEEE Computer Society, 2012:789796

Bretto A, Gillibert L. HypergraphBased image representation[C]// Iapr International Conference on GraphBased Representations in Pattern Recognition. SpringerVerlag, 2005:111

Zhou D, Huang J. Learning with hypergraphs: clustering, classification, and embedding[C]// International Conference on Neural Information Processing Systems. MIT Press, 2006:16011608

Comaniciu D, Meer P. Mean Shift: A Robust Approach Toward Feature Space Analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5):603619

Rital S, Cherifi H, Miguet S. Weighted Adaptive Neighborhood Hypergraph Partitioning for Image Segmentation[C]// International Confer ence on Pattern Recognition and Image Analysis. SpringerVerlag, 2005:522531

Yu J, Cheng J, Wang J, et al. Transductive Cartoon Retrieval by Multiple Hypergraph Learning[M]// Neural Information Processing. Springer Berlin Heidelberg, 2012:269276

Wang X, Tang Y, Masnou S, et al. A Global/Local Affinity Graph for Image Segmentation[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 2015, 24(4):1399

Liu Q, Sun Y, Wang C, et al. Elastic Net Hypergraph Learning for Image Clustering and Semisupervised Classification[J]. IEEE Transactions on Image Processing, 2016, PP(99):11

Wei W, Yang H, Wu Z, et al. A Novel Image Segmentation Algorithm Based on Multiple Features Fusion with Hypergraph and Super pixel[M]// Foundations of Intelligent Systems. Springer Berlin Heidelberg, 2014:709718

Xu C, Tao D, Xu C. A Survey on Multiview Learning[J]. Computer Science, 2013

Xia T, Tao D, Mei T, et al. Multiview Spectral Embedding[J]. IEEE Transactions on Systems Man and Cybernetics Part B, 2010, 40(6):1438 1446

Meila M, Shi J. A random walks view of spectral segmentation. AISTATS[J]. Ai and Statistics, 2001

Zhou D, Burges C J C. Spectral clustering and transductive learning with multiple views[C]// Machine Learning, Proceedings of the Twenty
Fourth International Conference. DBLP, 2007:11591166

Achanta R, Shaji A, Smith K, et al. SLIC Superpixels Compared to StateoftheArt Superpixel Methods[J]. IEEE Transactions on Pattern Analysis and Machine Inteligence, 2012, 34(11):2274

Yu J, Tao D, Wang M. Adaptive hypergraph learning and its application in image classification.[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 2012, 21(7):3262.

Karypis G, Aggarwal R, Kurnar V, et al. Multilevel hypergraph partition: applications in vlsi design[C]// Design Automation Conference. ACM, 1997:526529.

KoyutÃ¼rk M, Aykanat C. Iterativeimprovementbased declustering heuristics for multidisk databases , [J]. Information Systems, 2005,
30(1):4770.

Ducournau A, Bretto A, Rital S, et al. A reductive approach to hypergraph clustering: An application to image segmentation[J]. Pattern Recognition, 2012, 45(7):27882803.

Ding L, Yilmaz A. Interactive image segmentation using probabilistic hypergraphs[J]. Pattern Recognition, 2010, 43(5):18631873.

Huang Y, Liu Q, Metaxas D. ]Video object segmentation by hypergraph cut[C]// IEEE Computer Society Conference on Computer Vision and Pattern Recognition. DBLP, 2009:17381745.

Dalal N, Triggs B. Triggs, B.: Histograms of Oriented Gradients for Human Detection. In: CVPR[J]. 2005, 1(12):886893.

Cheng H D, Jiang X H, Sun Y, et al. Color image segmentation: advances and prospects[J]. Pattern Recognition, 2001, 34(12):22592281.

Zhang Y J. Advances in Image and Video Segmentation[J]. express shipping*, 2006(3).

Agarwal S, Lim J, Zelnikmanor L, et al. Beyond Pairwise Clustering[J]. 2013, 2:838 – 845.