ForegroundBack ground Segmentation using KMeans Clustering Algorithm and Support Vector Machine
Subject Areas : IT Strategy
Masoumeh
Rezaei
^{
1
}
(Faculty of Electrical and Computer Engineering, University of Sistan and Baluchestan, Zahedan, Iran)
mansoureh
rezaei
^{
2
}
(Computer Engineering Department, Faculty of Engineering, Yazd University, Yazd, Iran)
Masoud
Rezaei
^{
3
}
(Faculty of Electrical Engineering, K. N. Toosi University of Technology, Tehran, Iran)
Keywords: ForegroundBackground Segmentation, Support vector machine, kmeans clustering, saliency map,
Abstract :
Foregroundbackground image segmentation has been an important research problem. It is one of the main tasks in the field of computer vision whose purpose is detecting variations in image sequences. It provides candidate objects for further attentional selection, e.g., in video surveillance. In this paper, we introduce an automatic and efficient Foregroundbackground segmentation. The proposed method starts with the detection of visually salient image regions with a saliency map that uses Fourier transform and a Gaussian filter. Then, each point in the maps classifies as salient or nonsalient using a binary threshold. Next, a hole filling operator is applied for filling holes in the achieved image, and the areaopening method is used for removing small objects from the image. For better separation of the foreground and background, dilation and erosion operators are also used. Erosion and dilation operators are applied for shrinking and expanding the achieved region. Afterward, the foreground and background samples are achieved. Because the number of these data is large, Kmeans clustering is used as a sampling technique to restrict computational efforts in the region of interest. K cluster centers for each region are set for training of Support Vector Machine (SVM). SVM, as a powerful binary classifier, is used to segment the interest area from the background. The proposed method is applied on a benchmark dataset consisting of 1000 images and experimental results demonstrate the supremacy of the proposed method to some other foregroundbackground segmentation methods in terms of ER, VI, GCE, and PRI.
[1] X. Y. Wang, W. W. Sun, Z. F. Wu, H. Y. Yang, "Color image segmentation using PDTDFB domain hidden Markov tree model", Applied Soft Computing, Vol. 29, 2015, pp. 138152.
[2] A. Dirami, K. Hammouche, M. Diaf, P. Siarry, P., "Fast multilevel thresholding for image segmentation through a multiphase level set method", Signal processing, 93(1), 2013, pp. 139153.
[3] H. Cai, Z. Yang, X. Cao, W. Xia, X. Xu, "A new iterative triclass thresholding technique in image segmentation", IEEE transactions on image processing, Vol. 23, No. 3, 2014, pp.10381046.
[4] L. U. Ambata and E. P. Dadios, "Foreground Background Separation and Tracking", International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment (HNICEM), 2019, pp. 16.
[5] F. A. Khan, M. Nawaz, M. Imran, A. U. Rahman and F. Qayum, "Foreground detection using motion histogram threshold algorithm in highresolution large datasets", Multimedia Systems, 2020, pp. 112.
[6] M. CastilloMartinez, F. J. GallegosFunes, B. E. Carvajal Gamez, G. UrriolagoitiaSosa, A. J. RosalesSilva, "Color index based thresholding method for background and foreground segmentation of plant images", Computers and Electronics in Agriculture, Vol. 178, 2020, p. 105783.
[7] J. Canny, "A computational approach to edge detection", IEEE Transactions on pattern analysis and machine intelligence, Vol. 93, No. 6, 1986, pp. 679698.
[8] J. M. Prewitt, "Object enhancement and extraction", Picture processing and Psychopictorics, Vol. 10, No. 1, 1970, pp. 1519.
[9] R. C. Gonzalez and R. E. Woods, "Digital image processing", 2002.
[10] T. Uemura and G. Koutaki and K. Uchimura, "T. Uemura and G. Koutaki and K. Uchimura", International Journal of Innovative computing, Information and control, Vol. 7, No. 10, 2011, pp. 60736083.
[11] D. DÃazPernil, A. Berciano, F. PeÃ±aCantillana and M. A. GutiÃ©rrezNaranjo, "Segmenting images with gradientbased edge detection using membrane computing", Pattern Recognition Letters, Vol. 34, No. 8, 2013, pp. 846855.
[12] C. Panagiotakis, I. Grinias and G. Tziritas, "Natural image segmentation based on tree equipartition, bayesian flooding and region merging", IEEE Transactions on Image Processing, Vol. 20, No. 8, 2011, pp. 22762287.
[13] J. Ning, D. Zhang and C. Wu and F. Yue, "Automatic tongue image segmentation based on gradient vector flow and region merging", Neural Computing and Applications, Vol. 21, No. 8, 2012, pp. 18191826.
[14] L. Wang, H. Wu and C. Pan, "Regionbased image segmentation with local signed difference energy", Pattern Recognition Letters, Vol. 34, No. 6, 2013, pp. 637645.
[15] S. E. Ebadi and E. Izquierdo, "Foreground segmentation with treestructured sparse RPCA", IEEE transactions on pattern analysis and machine intelligence, Vol. 40, No. 9, 2017, pp. 22732280.
[16] Y. Boykov, O. Veksler and R. Zabih, "Fast approximate energy minimization via graph cuts", IEEE Transactions on pattern analysis and machine intelligence, Vol. 23, No. 11, 2001, pp. 12221239. [17] T.M. Nguyen and Q. J. Wu, "Fast and robust spatially constrained Gaussian mixture model for image segmentation", IEEE transactions on circuits and systems for video technology, Vol. 23, No. 4, 2012, pp. 621635.
[18] O. O. Karadag and F. T. Y. Vural, "Image segmentation by fusion of low level and domain specific information via Markov Random Fields", Pattern Recognition Letters, Vol. 46, 2014, pp. 7582.
[19] N. Dhanachandra, K. Manglem and Y. J. Chanu, "Image segmentation using Kmeans clustering algorithm and subtractive clustering algorithm", Procedia Computer Science, Vol. 54, 2015, pp. 764771.
[20] Y. Yang, Y. Wang and X. Xue, "A novel spectral clustering method with superpixels for image segmentation", Optik, Vol. 127, No. 1, 2016, pp. 161167.
[21] L. A. Lim and H. Y. Keles, "Foreground segmentation using convolutional neural networks for multiscale feature encoding", Pattern Recognition Letters, Vol. 112, 2018, pp. 256262.
[22] A. Shahbaz and K. H. Jo, "Deep Foreground Segmentation using Convolutional Neural Network", IEEE 28th International Symposium on Industrial Electronics (ISIE), 2019, p. 103334.
[23] P. Patil and S. Murala, "Fggan: A cascaded unpaired learning for background estimation and foreground segmentation", IEEE Winter Conference on Applications of Computer Vision (WACV), 2019, pp. 17701778.
[24] D. Sakkos and E. S. Ho and H. P. Shum, "Illuminationaware multitask GANs for foreground segmentation", IEEE Access, Vol. 7, 2019, pp. 1097610986.
[25] J. Liang and Y. Xue and J. Wang, "Genetic programming based feature construction methods for foreground object segmentation", Engineering Applications of Artificial Intelligence", Vol. 89, 2020, p. 103334.
[26] Z. Yu, H. S. Wong and G. Wen, "A modified support vector machine and its application to image segmentation", Image and Vision Computing, Vol. 29, No. 1, 2011, pp. 2940.
[27] X. Y. Wang, Q. Y. Wang, H. Y. Yang and J. Bu, "Color image segmentation using automatic pixel classification with support vector machine", Neurocomputing, Vol. 74, No. 18, 2011, pp. 38983911.
[28] X. Bai and W. Wang, "SaliencySVM: An automatic approach for image segmentation", Neurocomputing, Vol. 136, 2014, pp. 243255.
[29] M. K. Sangale and N. B. Kadu, "Realtime Foreground Segmentation and Boundary Matting for Live Videos using SVM".
[30] C. Tang and M. O. Ahmad and C. Wang, "Foreground segmentation in video sequences with a dynamic background", 11th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics (CISPBMEI), 2018, pp. 16.
[31] L. U. Shuhan and S. J. YE, "Using an image segmentation and support vector machine method for identifying two locust species and instars", Journal of Integrative Agriculture, Vol. 19, No. 5, 2020, pp. 13011313.
[32] N. Dhanachandra, K. Manglem, and Y. Chanu, "Image segmentation using Kmeans clustering algorithm and subtractive clustering algorithm". Procedia Computer Science, 54, 2015, pp. 764771.
[33] W. Chen, C. He, C. Ji, M. Zhang, S. and Chen, "An improved Kmeans algorithm for underwater image background segmentation", Multimedia Tools and Applications, 80(14), 2021, pp. 2105921083.
[34] Y. Yang, H. Bilen, Q. Zou, W. Y. Cheung, X. Ji, "Learning ForegroundBackground Segmentation from Improved Layered GANs", In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (pp. 25242533), 2022.
[35] B. E. Boser, I. M. Guyon and V. N. Vapnik, "A training algorithm for optimal margin classifiers", In Proceedings of the fifth annual workshop on Computational learning theory, 1992, pp. 144152.
[36] V. N. Vapnik, "Statistical learning theory", Wiley, New York, 1998.
[37] M. A. Aizerman,"Theoretical foundations of the potential function method in pattern recognition learning",Automation and remote control, Vol. 25, 1964, pp.821837.
[38] S. Lloyd,"Least squares quantization in PCM", IEEE transactions on information theory, Vol. 28, No. 2, 1982, pp. 129137.
[39] C. Guo and L. Zhang, "A novel multiresolution spatiotemporal saliency detection model and its applications in image and video compression", IEEE transactions on image processing, Vol. 19, No. 1, 2009, pp. 185198.
[40] P. Soille, "Morphological image analysis: principles and applications", Springer Science and Business Media, 2013.
[41] R. Achanta and Sh. Hemami and F. Estrada and S. Susstrunk, "Frequencytuned salient region detection", IEEE conference on computer vision and pattern recognition, 2009, pp. 15971604.
[42] R. Unnikrishnan, C. M. Pantofaru and M. Hebert, "Toward objective evaluation of image segmentation algorithms", IEEE transactions on pattern analysis and machine intelligence, Vol. 29, No. 6, 2007, pp.929944.
[43] M. Meila,"Comparing clusteringsâ€”an information based distance",Journal of multivariate analysis, Vol. 98, No. 5, 2007, pp. 873895.
[44] D. Martin and C. Fowlkes and D. Tal and J. Malik, "A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics", Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, Vol. 2, 2001, pp. 416423.
ForegroundBack ground Segmentation using KMeans Clustering Algorithm and Support Vector Machine 
Masoumeh Rezaei1*, Mansoureh Rezaei2 , Masoud Rezaei3

1. Faculty of Electrical and Computer Engineering, University of Sistan and Baluchestan, Zahedan, Iran 2. Computer Engineering Department, Faculty of Engineering, Yazd University, Yazd, Iran 3. Faculty of Electrical Engineering, K. N. Toosi University of Technology, Tehran, Iran 
Received: 10 Jun 2021/ Revised: 04 Apr 2022/ Accepted: 06 May 2022 

Abstract
Foregroundbackground image segmentation has been an important research problem. It is one of the main tasks in the field of computer vision whose purpose is detecting variations in image sequences. It provides candidate objects for further attentional selection, e.g., in video surveillance. In this paper, we introduce an automatic and efficient Foregroundbackground segmentation. The proposed method starts with the detection of visually salient image regions with a saliency map that uses Fourier transform and a Gaussian filter. Then, each point in the maps classifies as salient or nonsalient using a binary threshold. Next, a hole filling operator is applied for filling holes in the achieved image, and the areaopening method is used for removing small objects from the image. For better separation of the foreground and background, dilation and erosion operators are also used. Erosion and dilation operators are applied for shrinking and expanding the achieved region. Afterward, the foreground and background samples are achieved. Because the number of these data is large, Kmeans clustering is used as a sampling technique to restrict computational efforts in the region of interest. K cluster centers for each region are set for training of Support Vector Machine (SVM). SVM, as a powerful binary classifier, is used to segment the interest area from the background. The proposed method is applied on a benchmark dataset consisting of 1000 images and experimental results demonstrate the supremacy of the proposed method to some other foregroundbackground segmentation methods in terms of ER, VI, GCE, and PRI.
Keywords: ForegroundBackground Segmentation; Support vector machine; kmeans clustering; saliency map.
1 Introduction
Image segmentation is one of the most significant image processing tasks in image analysis and understanding. The main goal of image segmentation is finding objects of interest from a given image using image characteristics such as color, texture, gray level and, so on. Typically, image segmentation methods can be categorized into six categories, Edge detectionbased methods, Histogram thresholdingbased methods, Graphbased methods, Regionbased methods, Statistical modelbased methods, and Machine learningbased methods [1].
Histogram thresholdingbased approaches use the assumption that adjacent pixels whose value lies within a certain range belong to the same class. Because of their intuitive properties, simplicity of implementation, and computational speed image, these techniques are widely used [26]. Edge detectionbased approaches assume that pixel values at the boundary between two regions change quickly. There are some edge detectors such as Canny [7], Prewitt [8], Sobel [9], and so on. The output of edge detectors provides candidates for the region boundaries. These algorithms are only suitable for noisefree and simple images [10,11]. The regionbased approaches assume that adjacent pixels in the same region have similar visual characteristics [1215]. By using these methods, pixels can be grouped into homogeneous regions that might be corresponding to an object.
In the Graphbased methods, an image is considered a weighted graph. Pixels and similarities between them are considered as nodes and edges of the graph, respectively. In these methods, image segmentation is measured as a problem of partitioning this graph into components with minimizing a cost function [1]. Graph cuts as one of the most important graphbased methods was introduced in 2001 [16].
Statistical modelbased methods use a statistical model that characterizes pixel values [17, 18]. Machine learningbased methods use machine learning techniques for image segmentation [1925]. In the last decade, some classification techniques have been successfully used in image segmentation. Especially, SVM as a binary classifier can be used for this purpose. In 2011, the Fast Support Vector Machine (FSVM) as a modified SVM was introduced for image segmentation [26]. Userselected objects and background pixels are used for training in this method. In the same year, Wang et al. applied Fuzzy CMeansSVM (FCMSVM) for color image segmentation [27]. In this method, training samples are selected randomly from the FCM clustering results. The drawback of this method is the number of FCM clusters must be set in advance, and the random selection of training samples also affects the performance of the final segmentation.
The saliencySVM (SSVM) method is a combination of visual saliency detection and SVM classification [28]. In this method, a trimap of the given image is extracted according to the saliency map for estimating the prominent locations of the objects. Positive and negative training sets are automatically selected for SVM training through histogram analysis in trimap. The entire highlighted object is segmented using a trained SVM classifier. In 2018, Sangale and Kadu introduced a realtime Foreground background segmentation using C1SVM (Competing 1 class Support Vector Machines) technique [29]. The method first trains local C1SVMs at every pixel area. Then, it relabels each pixel using learned C1SVM. In the next step, it performs matting along the foreground boundary and then it applies global optimization.
Tang et al. applied SVM for Foreground Segmentation in video sequences [30]. They introduced a novel feature image and used it in the framework of a support vector machine. In 2020, the SVM method is proposed for identifying two locust species and instars [31]. They used the Grab Cut method and principal component analysis for extracting eight features from 73 features of locusts. However, the proposed Image segmentation and feature extraction of this method are complicated which causes difficulty to achieve fully automatic identification.
In addition to the SVMbased methods, some other methods have been introduced in this field. Dhanachandra et al. used kmeans to segment the foreground area from the background. The subtractive clustering method is applied to generate the centroid based on the potential value of the data points. In this method, partial contrast stretching is used for improving the quality of the image and the middle filter is applied to improve the segmented image [32].
In 2021, Chen et al. proposed an improved Kmeans algorithm for underwater image background segmentation. The method deals with the problem of improper determination of the value of K and minimizes the effect of the initial centroid position of the grayscale image during the quantification of the gray surface of the conventional Kmeans algorithm [33].
In recent years, researchers have proposed some deep learning methods for the image segmentation. In 2022, Yang et al. proposed a generative adversarial deep network for foreground and background segmentation. The method avoids trivial decompositions by maximizing mutual information between generated images and latent variables [34].
In this paper, we propose a novel and efficient foregroundbackground segmentation. First, SVM is used for segmenting the interest area from the background. Then, Kmeans clustering is applied for selecting the training data of SVM. It restricts the computational efforts in the region of interest. However, before applying the Kmeans algorithm, the first saliency parts are selected using a saliency map and some efficient operators.
The rest of this paper is organized as follows. In Section 2, The SVM and KMeans methods are explained in detail. Section 3 describes the proposed method. Section 4 illustrates the experimental results. Finally, the paper is concluded in Section 5.
2 Primary Concepts
This section provides a detailed description of SVM and KMeans methods as the approaches along with the proposed method.
21 Support Vector Machine
SVM was proposed by Vapnik and coworkers [35]. It is a supervised learning method that originated from statistical learning theory. The main idea behind SVM is the separation of the two classes with a hyperplane that maximizes the margin between them. Maximizing margin results in minimizing structural risk. The basis of minimizing structural risk instead of empirical risk is an interesting property of SVM [36]. Thus, SVM outperforms other methods such as neural networks which are based on minimizing empirical risk. Also, its strong generalization reduces the influence of the noise. This method also can be considered a nonlinear classification using the kernel trick. The kernel maps their inputs into highdimensional feature spaces implicitly [37].
Consider the problem of separating the data set of N points with the input dataand the corresponding target . In feature space SVM models take the form:
 (1) 
where is a bias term and is a nonlinear function that maps the input space to a highdimensional space. The dimensionis implicitly defined that it can be infinitedimensional. SVM optimization problem for the linear separate case is:
 (2) 
and for the nonseparable case is:

(3) 
where parameter C is the regularization parameter that controls the tradeoff between the complexity of the model and the training error that needs to be specified a priori. A larger C means assigning a higher penalty to errors. The Lagrangian dual problem for the SVM is simply:

(4) 
whereare positive Lagrange multipliers and. Finally, the classification problem is solved using quadratic programming packages. The new data can be classified as follows:
 (5) 