IJCSNS International Journal of Computer Science and Network Security, VOL.13 No.11, November 2013

1

Moving Object Segmentation Method Based on Motion
Information Classification by X-means and Spatial Region
Segmentation
Kousuke Imamura
Institute of Science and Engineering, Kanazawa University
Kakuma-machi, Kanazawa, Ishikawa 920-1192 Japan
Summary
We here in propose a moving object segmentation method basedon motion information classification by x-means clustering andregion segmentation. In the proposed method, a current frame isfirst segmented by a morphological watershed algorithm. Affine
motion information obtaining from three frames at the featurepoints is classified by x-means clustering. Whether a featurepoint corresponds to an uncovered background region or an
occlusion is then estimated based on the temporal correlation of
the clustering results, and incorrect classified feature point is
excluded. Finally, a label is assigned to the segmented region
based on the clustering results of motion information. The
labeled region represents the moving object segmentation resultsof the proposed method. The experimental results reveal that the
proposed method provides good moving object segmentation fora suitable number of objects.

Key words:
Moving object segmentation, X-means clustering, Morphologicalwatershed algorithm

1. Introduction
The extraction/segmentation technique for semantic object
information in a video sequence is important. The obtained
moving object information is used for content based
applications, such as object-based video coding in MPEG4 and metadata for retrieval and/or editing of video scenes.
Although a number of approaches for moving object
extraction have been proposed [1]-[6], a general-purpose
technique with high accuracy has not yet been established.
Moreover, a number of these methods require constraint
conditions to be satisfied. Spatial- and temporalinformation based techniques often extract moving objects
from a still background [3] or a known background [4],and knowledge-based techniques require the rough shapeinformation to extract the target object [5]. For general
purpose extraction, it is desirable that there be noconstraint condition.
A moving object segmentation method based on region
merging has been proposed [6]. This method merges theimage regions having homogeneous motion, and theregion merging method does not require a constraint
condition of a still background or a known rough shape.
Manuscript received November 5, 2013
Manuscript revised November 20, 2013

However, it is difficult to discriminate the number ofobjects from the motion similarity between neighboring
regions because of the image dependence of the estimatedmotion. Therefore, we generally assign the number ofobjects, so that that number of objects being known is aconstraint condition.
In the present paper, we propose a moving object
segmentation technique based on classified motion
information by x-means clustering and spatial region
segmentation using a morphological watershed algorithm.
X-means clustering [7] is a classification algorithm thatprovides the optimal number of clusters based on theBayesian information criterion (BIC) [8]. In the proposed
method, the current frame is first segmented into regions
by the morphological watershed algorithm. The featurepoints are selected from the segmented regions and theaffine motion parameters are estimated from three frames
centered on the current frame for each feature point. A
label is assigned to the segmented region by voting for thecluster of the feature point in each region. The labeling
result represents the moving object segmentation results
for the proposed method. In particular, we introduce theexclusion of the unreliable feature point, the reduction of
the initial value dependence in x-means clustering, and theimprovement of labeling for the region in which motion
cannot be estimated.
The remainder of the present paper is organized as follows.
Section 2 presents the basic principle of x-meansclustering. Section 3 describes the algorithm of the
proposed moving object segmentation method.
Experimental results are presented in Section 4, andconcluding remarks are presented in Section 5.

2. Basic Principles of X-means Clustering
X-means clustering [7] provides classification with the
optimal number of clusters based on the BIC [8]. The
algorithm continues to divide the cluster into two newclusters by k-means clustering, and the iteration of thedivision process is stopped based on the BIC.

2

IJCSNS International Journal of Computer Science and Network Security, VOL.13 No.11, November 2013

In x-means clustering, cluster 𝐶𝑖 is applied by k-means
algorithm with setting k = 2. The divided clusters aredesignated 𝐶𝑖1 and 𝐶𝑖2 . We assume the following pdimensional normal distribution for the data 𝐱 𝑖 containedin 𝐶𝑖 :𝑓(𝜃𝑖 ; 𝐱) =1

�(2𝜋)𝑝 |𝐕|

exp �−(𝐱 − 𝜇𝑖 )𝑡 𝐕𝑖−1 (𝐱 − 𝜇𝑖 )
�
2

(1)

and then calculate the BIC as follows:

BIC = −2log𝐿�𝜃�𝑖 ; 𝐱 ∈ 𝐶𝑖 � + 𝑞log𝑛𝑖(2)

�𝑖 � is the maximum likelihood estimate ofwhere 𝜃�𝑖 = �𝜇̂ 𝑖 , 𝐕
the p-dimensional normal distribution, 𝜇𝑖 is the pdimensional means vector, and 𝐕𝑖 is the p×p-dimensionalvariance-covariance matrix, and, q is the number ofdimensions of the parameters, where q = 2p if we assume
that the covariance components of 𝐕𝑖 are ignored. Finally,𝑛𝑖 is the number of elements contained in 𝐶𝑖 , 𝐿 is thelikelihood function and 𝐿(∙) = ∏ 𝑓(∙).
The BICs of the target cluster are calculated before andafter division by the k-means clustering and the BICs arecompared. If the BIC after division is less than the BIC
before division, the data distribution in the clusters after
division are set to closer to a multivariate normal
distribution than that before division, and the cluster isdivided into two clusters. If the BIC before division is lessthan that after division, we prefer not to divide additional
clusters. The above process is iterated until division is not
carried out in all clusters. As a result, the clustering
algorithm provides the division with the optimal numberof clusters.

3. Moving Object Segmentation Method
Using X-means Clustering and Region
Segmentation
We describe the proposed moving object segmentation
method using x-means clustering and region segmentation.
Figure 1 shows a schematic diagram of the proposed
moving object segmentation algorithm.

3.1 Spatial Region Segmentation
Morphological Watershed Algorithm

over-segmentation. As a countermeasure, we apply themorphological watershed algorithm, which includes
morphological processing for the prevention of oversegmentation. In the morphological watershed, a current
frame is processed by improved opening-closing [10],multi-scale gradient processing [11], and morphologicalreconstruction [12]. The process provides the smoothed
gradient while maintaining the object edge and thewatershed algorithm is applied to the obtained gradientimage. The processing result is the spatial region
segmentation of the proposed method.

using

the

In the first step of the proposed method, the current frame
is segmented spatially by the morphological watershedalgorithm based on intensity information.
The boundary of the segments by the typical watershedalgorithm [9] is in accordance with the edge of the object,
but the influence of noise and the lighting condition lead toFig. 1 Proposed motion object segmentation algorithm.

3.2 Feature Point Extraction and Bi-directional
Motion Estimation
In the next step, the feature points are extracted in eachregion of the segmented image. We select the featurepoints using a Harris corner detector [13] for accurate
motion estimation. Then, the maximum number of featurepoints in a region is set to 100 and the minimum distance
between the neighboring feature points is constrained to be
more than 𝑙𝑚𝑖𝑛 = log 2 (𝑆𝑟 ⁄100) where 𝑆𝑟 denotes thearea of each region.
Next, we estimate the bi-directional affine motion
parameters at feature points from the previous frame to thecurrent frame and from the current frame to the next frame.
A translation motion vector of the feature point isestimated using the block matching method. The objectivefunction is defined as follows:
𝐷𝐵𝐷(𝑃) = � {𝐼𝑡 (𝑃𝑖 ) − 𝐼𝑡−1 (𝑃𝑖 + 𝐝)}2
𝑃𝑖 ∈𝐵(𝑃)(3)

where 𝐼𝑡 (𝑃) is the intensity at feature point 𝑃 in thecurrent frame and 𝐼𝑡−1 (𝑃 + 𝐝) is the intensity of theposition with displacement 𝐝 = (𝑑𝑥 , 𝑑𝑦 ) from featurepoint P in the previous frame. Moreover, 𝐵(𝑃) denotes the

IJCSNS International Journal of Computer Science and Network Security, VOL.13 No.11, November 2013

block centered at the feature point P. In the present paper,
the block size of 𝐵 is set to 15 × 15 pixels, and thesearching range is set to ±7 pixels.
The affine motion parameter of the feature point iscalculated by the Gauss-Newton iterative algorithm
starting with the obtained translation vector as the initial
vector. The displacement (𝑣𝑥 (𝑥, 𝑦), 𝑣𝑦 (𝑥, 𝑦)) of the affine
motion model is given as𝑣𝑥 (𝑥, 𝑦) = 𝑎𝑥 + 𝑏𝑦 + 𝑐,𝑣𝑦 (𝑥, 𝑦) = 𝑑𝑥 + 𝑒𝑦 + 𝑓(4)

where (𝑥, 𝑦) denotes the image coordinates, a, b, d and edenote the rotation and scaling parameters, and c and fdenote the translation parameters. Similarly, the affine
motion parameters from the current frame 𝐼𝑡 to the next
frame 𝐼𝑡+1 are also calculated.
An inaccurate affine motion parameter has adverse
influence on the classification process. Thus, feature points
having low intensity variance or high prediction error are
excluded from the data for clustering as feature points thatcannot obtain accurate motion. The exclusion conditions inthis processing are given as follows:
𝜎𝐼2 < 𝑇𝐼�
� + 2𝜎𝐸𝑟𝑟
𝐸𝑟𝑟(𝑃) > 𝐸𝑟𝑟(5)

where 𝜎𝐼2 denotes the intensity variance of the blockcentered at the feature point and 𝑇𝐼 is the threshold used todecide the reliability for the intensity variance, which is set
� 𝑒 and 𝜎𝐸𝑟𝑟 denote theto 1.0 in the present paper. 𝐸𝑟𝑟
median value and the standard deviation, respectively, ofthe logarithmic prediction error.

3.3 Motion Information Classification by X-means
Clustering
Feature points are classified based on the estimated bidirectional affine motion parameters by x-means clustering.
If the object is rigid, the feature points in each object areclassified into separate clusters. In the proposed method,
the dimension p of the affine motion parameter is six.
In the proposed method, the classification process formotion information is important. Thus, we reduce theinitial value dependence for x-means clustering and deleteof insignificant cluster and the unreliable feature points for
improvement.
X-means clustering depends on the initial value like kmeans clustering. In the x-means clustering, unsuitable
initial cluster value leads to over-clustering. In order toprovide improved clustering, we merge the clusters which
the center distance is nearest after convergence of thedivision processing. In the processing, the BICs arecalculated before and after merging. The clusters ismerged for the data distribution more similar to model

3

distribution if the BIC after merging is less than that
before cluster merging. As a result of this processing, theproblem of the original cluster being divided into multiple
clusters due to the initial cluster value is mitigated.
On the other hand, the data distribution is assumed to be ap-dimensional normal distribution, but the estimatedmotion information at the feature points includes
inaccurate motion information because of the influence ofnoise or uncovered background and occluded areas. The
data is then classified into multiple clusters, the number ofwhich exceeds the actual number of objects. Thus, weremove clusters that contain fewer than the average
number of feature points in one region as insignificant
cluster.
If a feature point exists in a region of uncovered
background or in an occluded area, the bi-directionalmotions at the feature point are often classified into
different clusters, although the motions are for the samefeature point. Therefore, the unreliable feature points forwhich the bi-directional motions are classified into
different clusters are excluded from the labeling process.

3.4 Labeling of Segmented Region by Voting
Finally, we assign a label that indicates whether eachsegmented region is an object or background forconsistency with the spatial region segmentation and theclassification result of the motion information. The label isdecided by voting for the cluster of the feature point ineach region. Therefore, an object represents regions having
the same label.
If the region does not include a sufficient feature point
because of the reliability decision described in Section 3.3,
the region is not assigned a label. The region is designatedan unlabeled region.
The unlabeled region is assigned a label by the following
procedure. First, the unlabeled region in the uncovered
background is detected by inverse mapping using thealready labeled region and the motion information. If theunlabeled region is included in the uncovered background,the label of the covered object is not assigned to the region.
Then the unlabeled region is assigned by voting using the
motion of the excluded unreliable feature point. If theunlabeled region includes a feature point such as theregion at end of the image, the region merges theneighboring region that has the most similar averageintensity. The labeling results for all regions represent theresults of the proposed moving object segmentation.

4. Simulation and Results
The moving object segmentation of the proposed method
was evaluated through computer simulations. “Penguin
and Dog” (320 × 240 pixels, grayscale) and “Intersection”(352 × 240 pixels, grayscale) were used as test sequences.

4

IJCSNS International Journal of Computer Science and Network Security, VOL.13 No.11, November 2013

The “Penguin and dog” sequence includes two different
moving objects: a penguin moving toward the right and adisk with an image of a dog rotates clockwise in the
background. The “Intersection” sequence includes three
moving cars and a number of pedestrians.

Fig. 2 Result of spatial region segmentation (113 regions).

Fig. 3 Extracted feature points and motions (5,159 points).

We first verified the results of each processing by the
proposed method for the “Penguin and Dog” sequence.
Figure 2 shows the spatial region segmentation results
obtained by the morphological watershed algorithm. The
number of segmented regions was 113. Figure 3 shows theextracted feature points and the translation component of
the estimated motions. The total number of feature points
was 5,159. Figure 3 indicates that the distribution of thefeature points was uniform in each region, and accurate
motion was obtained for most of the feature points.
Erroneous motions were detected at the feature points inthe uncovered background, such as behind the penguin,although there was no movement in this region.

Table 1 Classification results

Penguin and Dog (frame no.54)
One-direction
Number of dataNo.
(4,594)
1
3,648
2
337
3
244
4
94
5
62
6
57
7
26
8
24
9
24
10
14
11
14

No.
1
2
3
4
5
6
7
8
9
10

Bi-direction
Number of data
(9,167)
7188
911
756
68
62
47
42
35
31
27

Next, we verified the classification results by x-meansclustering for the affine motion parameters. Table 1 shows
the number of data in each cluster for one-directional andbi-directional motion information. Based on these results,
the one-directional motion data were classified into 11
clusters and the bi-directional motion data were classified
into 10 clusters. In Table 1, the shaded clusters indicate
significant clusters that include more data than the averagefeature points in the region. The feature points insignificant clusters are only used for labeling. In the caseof the classification of bi-directional motion, unreliablefeature points in uncovered background regions or
occluded areas are excluded in order to improveclassification processing.
Figure 4 shows the unreliable feature points obtained
based on the classification of bi-directional motion. Figure
4 indicates that unreliable feature points exist in theuncovered background and occluded regions, and weverified the correctness of the unreliable feature pointdeletion.
Figure 5 shows the result of region labeling by voting
using feature point classified based on one-directionalmotion or bi-directional motion. In the figure, the samelabel is indicated by the same color. From Figure 5, thenumber of objects obtained for one-directional motion was
four and the number of objects obtained using bidirectional motion was three. “Penguin and Dog” sequence
includes two objects and the background. The
segmentation results obtained using bi-directional motion
provided the actual number of objects and were moreaccurate.

IJCSNS International Journal of Computer Science and Network Security, VOL.13 No.11, November 20135

object segmentation. The results of the proposed method
were also compare with the results of the region merging
method [14] in which the regions are merged based on thedisplacement of affine motion parameter after merging
processing.
Table 2 Accuracy evaluation of moving object segmentation.

MethodFig. 4 Unreliable feature points based on bi-direction motion
classification.

Regionmerging

4

116/5

95.9

Proposed

3

118/3

97.5

Method(a)(b)
Fig. 5 Results of (a) labeling based on one-directional motion
classification and (b) labeling based on bi-directional motion
classification.

Next, we estimate the accuracy of the proposed moving
object segmentation method. Figure 6 shows the moving
object segmentation results. “Penguin and Dog” and“Intersection” were used as test sequences. The results ofthe proposed method were compared with the labeling
result obtained by human viewing as the accurate moving

Penguin and Dog (frame no.42)
Number of
Accuracy
Numberaccurate region
rateof object(True/False)[%]

Intersection (frame no.275)
Number of
Numberaccurate regionof object(True/False)

Accuracy
rate[%]

Regionmerging6

109/1985.2

Proposed3

117/11

91.4

The number of the segmented objects in “Penguin and Dog”
and “Intersection” obtained by the proposed method wasthree for both sequences. Using the region merging
method, the number of segmented objects obtained in“Penguin and Dog” was four and that in “Intersection” wassix. The region merging method merged regions until
subjective failure of merging. The segmentation results ofthe proposed method for “Penguin and Dog” were goodsegmentation both the number of objects and the accuracy
than that of region merging. The segmentation results ofthe proposed method for “Intersection” did not segment
some small objects, although significant object that the carat center of the sequence was segmented more accuratelyby the proposed method than the region merging method.
Table 2 shows the accuracy evaluation of the proposed method
and the region merging in comparison to the subjective labeling
results. The accuracy rate is defined as the ratio of the correctly
extracted region to all of the regions. For the “Penguin and Dog”
sequence, the accuracy rate of the proposed method was 97.5%
and the accuracy rate of the region merging was 95.9%. For the“Intersection” sequence, the accuracy rate of the proposed
method was 91.4% and the accuracy rate of the region merging
was 85.2%. The results revealed that the proposed method
provides more accurate moving object segmentation than theregion merging method and that the number of segmented
regions obtained by the proposed method was similar to theactual number of objects in the sequences.

6

IJCSNS International Journal of Computer Science and Network Security, VOL.13 No.11, November 2013

(a)

(b)

(c)

(d)
Fig. 6 (a) Original “Penguin and Dog” and “Intersection” sequences, Moving object segmentation results obtained (b) after labeling by human viewing, (c)using region merging, and (d) using the proposed method.

IJCSNS International Journal of Computer Science and Network Security, VOL.13 No.11, November 2013

5. Conclusions
We herein proposed a moving object segmentation method
based on motion information classification by x-meansclustering and spatial region segmentation. In the proposed
method, the affine motion parameter of bi-directionalmotion of the feature point is classified by x-meansclustering. Labels are assigned to the segmented regions,which are obtained by the morphological watershedalgorithm, by voting for the cluster of feature points ineach region. The simulation results revealed that the
proposed method provides moving object segmentation fora suitable number of objects. In the future, we intend to
improve the label assignment for small regions withinaccurate motion.

References[1] T. Schoenemann and D. Cremers, “Near Real-time Motion
Segmentation Using Graph Cuts,” Springer, LNCS 4174,
pp.455-464, 2006.
[2] Y. Wang, K.-F. Loe, T. Tan and J.-K. Wu, “Spatiotemporal
Video Segmentation Based on Graphical Models,” IEEE
Trans. Image Process., Vol.14, No.7, pp.937-947, 2005.
[3] L.-H. Chen, Y.-C. Lai, C.-W. Su and H.-Y. M. Liao,“Extraction of Video Object with Complex Motion,” Pattern
Recognition Letters, Vol.25, No.11, pp.1285-1291, 2004.
[4] S. Sakaida, M. Naemura and Y. Kanatsugu, “Moving Object
Extraction Using Background Difference and Region
Growing with a Spatiotemporal Watershed Algorithm,”
Systems and Computers in Japan, Vol.33, No.12, pp.11-26,
2002.
[5] I. Dagher and K. E. Tom, “WaterBalloons: A Hybrid
Watershed Balloon Snake Segmentation,” Image and Vision
Computing, Vol.26, No.7, pp.905-912, 2008.
[6] F. Mochieni,S. Bhattacharjee and M. Kunt, “Spatiotemporal
Segmentation Based on Region Merging,” IEEE Trans.
Pattern Anal. Machine Intell., Vol.20, No.9, pp.897915 ,1998.
[7] T. Ishioka, “An Expansion of X-means for Automatically
Determining the Optimal Number of Clusters”, Proc. of The
4th IASTED International Conference on Computational
Intelligence, pp.91-96, 2005.
[8] J. M. Jolion, P. Meer and S. Bataouche, “Robust Clusteringwith applications in Computer Vision,” IEEE Trans. PatternAnal. Machine Intell., Vol.13, No.8, pp.791-802, 1991.
[9] L.Vincent and P. Soille, “Watersheds in Digital Spaces: An
Efficient Algorithm Based on Immersion Simulations,”
IEEE Trans. Pattern Anal. Machine Intell., Vol.13, No.6,
pp.583-598, 1991.
[10] D. Cortez, et al., “Image Segmentation Towards New Image
Representation Methods,” Signal Processing: Image
Communication, Vol.6, pp.485-498, 1995.
[11] D. Wang, “A Multiscale Gradient Algorithm for Image
Segmentation Using Watersheds,” Pattern Recognition,
Vol.30, No.12, pp.2043-2052, 1997.

7[12] D.Vincent, “Morphological Grayscale Reconstruction in
Image Analysis: Applications and Efficient Algorithm,”
IEEE Trans. Image Process., Vol.2, No.2, pp.177-201, 1993.
[13] C. Harris and M. Stephans, “A Combined Corner and Edge
Detection,” Proc. of The fourth Alvey Vision Conference,
pp.147-151, 1988.
[14] K. Imamura and H. Hashimoto, “Merging of Moving
Regions Based on Robust Estimation for Affine Motion
Parameters,” The Journal of The Institute of Image
Information and Television Engineers, Vol.63, No.11, pp.15, 2009.
[15] K. Imamura, N. Kubo and H. Hashimoto, “AutomaticMoving Object Extraction Using X-means Clustering,” Proc.
of 28th Picture Coding Symposium, pp.246-249, 2010.

Kousuke Imamura
received the
B.S., M.S. and Dr. Eng. degrees inElectrical Engineering and Computer
Science in 1995, 1997 and 2000,
respectively, all from Nagasaki University.
He is currently an Associate Professor in
the Institute of Science and Engineering at
Kanazawa University. His researchinterests are image processing and highefficiency image coding.