Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. V (2010), No. 2, pp. 193-204 Objects Detection by Singular Value Decomposition Technique in Hybrid Color Space: Application to Football Images M.Moussa Jlassi, A. Douik, H. Messaoud Mourad Moussa Jlassi Ecole Nationale d’Ingénieurs de Monastir Avenue Ibn El Jazzar - 5019 - Monastir - TUNISIE E-mail: Mourad.enim@yahoo.fr Ali Douik and Hassani Messaoud Ecole Nationale d’Ingénieurs de Monastir Avenue Ibn El Jazzar - 5019 - Monastir - TUNISIE E-mail: Ali.douik@enim.rnu.tn E-mail: Messaoud.hassani@enim.rnu.tn Abstract: In this paper, we present an improvement non-parametric background modeling and foreground segmentation. This method is important; it gives the hand to check many states kept by each background pixel. In other words, generates the historic for each pixel, indeed on certain computer vision applications the background can be dynamic; several intensities were projected on the same pixel. This paper describe a novel approach which integrate both Singular Value Decomposition (SVD) of each image to increase the compactness density distribution and hybrid color space suitable to this case constituted by the three relevant chromatics levels deduced by histogram analysis. In fact the proposed technique presents the efficiency of SVD and color information to subtract background pixels corresponding to shadows pixels. This method has been applied on colour images issued from soccer video. In the other hand to achieve some statistics information about players ongoing of the match (football, handball, volley ball, Rugby...) as well as to refine their strategy coach and leaders need to have a maximum of technical-tactics information. For this reason it is prominent to elaborate an algorithm detecting automatically interests color regions (players) and solve the confusion problem between background and foreground every moment from images sequence. Keywords: Segmentation, Color Image, Statistic Algorithm, Histogram Analysis, Singular Value Decomposition. 1 Introduction Image segmentation based on background modeling is a research thematic up until now locates on the head of enormous number of studies. Indeed background modeling and image segmentation tech- niques leads to remedy many problems in a wide spectrum of computer vision applications; K. Elgammal et al. [1] present non-parametric model for the images segmentation when the background is dynamic. Ying Ming et al. [2] propose a statistical algorithm inspired from the idea of Elgammal based on Cauchy distribution; they proved that the intensity values of background pixels are adapted to Cauchy’s distri- bution. O. Javed et al. [3], propose mixture models to handle the backgrounds that exhibit multimodal characteristics, integration of gradient information are suggested as another feature of the multiple mod- els. Although Gaussian mixture models can converge to any arbitrary distribution provided by enough Copyright c⃝ 2006-2010 by CCC Publications 194 M.Moussa Jlassi, A. Douik, H. Messaoud number of components. R. Agarwal et al. [4] present a data-hiding algorithm that exploit the singular value decomposition (SVD) representation of the data. They compute the SVD of the host image and the watermark and embed the watermark in the singular vectors of the host image. The proposed method leads to an imperceptible scheme for digital images, both in grey scale and color and is quite robust against attacks like noise and JPEG compression. In this paper, we describe an algorithm modeling and subtracting the background pixels based on SVD approach which is used in many computer vision problems on one hand, select the appropriate color space among the wide set of color levels commonly used in color image analyze on the other hand. Both compactness power of various density distributions and quality of approximated image are increased by singular value decomposition approach. Also this technique can be used to answer several purpose for example eliminate noise and highlights [5, 6] issues from the change of illuminations, dy- namic background pixels, camera displacement and shadows. Finally specify the suitable color space constituted by the three significant color levels, where this segmentation technique will be realized and use a new similarity measure between reference and candidate image that consists to calculate the inter- section coefficients of color histogram images. This paper is organized as follows. Section 2 presents an overview of statistical algorithms and background model. In section 3 we define the singular value decomposition and we describe the main issues of the SVD approach. Hybrid color space constituted by significant levels has been explained in section 4. Finally, section 5 describes foreground segmentation and experimental results which will evaluate the robustness of this technique. 2 An overview of statistical algorithms and background model 2.1 Statistical Algorithms A large variety of Background subtraction and image segmentation’s algorithms have been developed in last few years ranging from parametric to non-parametric, from pixel to region [8]. Statistical algo- rithms are frequently used in computer vision; M. Seki et al. [7] propose background subtraction based on Cooccurrence of image variations. Oriol Pujol et al. [9] propose a new deformable model defined in a statistical framework to segment objects of natural scenes. They perform a supervised learning of local appearance of the textured objects and construct a feature space using a set of co-occurrence matrix measures. Linear Discriminant Analysis allows them to obtain an optimal reduced feature space where a mixture model is applied to construct a likelihood map. Instead of using a heuristic potential field, their active model is deformed on a regularized version of the likelihood map in order to segment objects characterized by the same texture pattern. Different tests on synthetic images, natural scene and medical images show the advantages of their statistic deformable model. K. Verma et al. [10] propose a new improved mountain clustering technique, which is compared with some of the existing techniques such as K-Means, FCM, EM and Modified Mountain Clustering. The performance of all these clustering techniques towards color image segmentation is compared in terms of cluster entropy as a measure of information and observed via computational complexity. The cluster entropy is heuristically determined, but is found to be effective in forming correct clusters as verified by visual assessment. A. Farhadi et al. [11] present a method for the segmentation of images based on local higher order statistics. The algorithm can be applied for the separation of objects from a texture background and the segmentation of textures. The proposed technique makes no use of a data bank and its complexity is O(χ) where χ is the number of pixels. Objects Detection by Singular Value Decomposition Technique in Hybrid Color Space: Application to Football Images 195 2.2 Non-parametric Background Model Because the parametric background model still lacks flexibility when the background pixels are dy- namic, a highly flexible non-parametric technique is proposed to estimate background probabilities from many recent samples over time using Kernel density estimation. In the non-parametric model all recently observed pixel values x1, x2,.. xN are modeled by probability density functions using a certain kernel esti- mator function, which is often chosen to be a Gaussian. The weighted sum of all these Gaussians results in the final probability density function of the pixel value xt : P(xt) = 1 n N∑ i=1 K(xt − xi) (1) The kernel estimator function K is chosen as a Normal function N(0,Σ) where Σ is the kernel function bandwidth. Color channels are assumed independent and each channel has its own kernel band width σ 2. These assumptions lead us to the final density estimation which can be written as: Pr(xt) = 1 K k∑ i=1 d∏ j=1 1√ 2π σ 2j exp− (xt j − xi j)2 2σ 2j (2) When this probability is higher than a certain threshold which is a global threshold over all the image, the pixel is classified as a foreground pixel. In other applications using kernel density estimation the kernel bandwidth dependent on the number of samples. To estimate the kernel band width σ 2 for the jth color channel for a given pixel we compute the median absolute deviation over the sample for consecutive intensity values of the pixel. That is, the median, m, of |xi − xi+1| for each consecutive pair (xi,xi+1) in the sample, is calculated independently for each color channel. If we assume that the distribution is Normal N(µ,σ 2), then the deviation (xi − xi+1) is Normal N(0,2σ 2). So the standard deviation of the first distribution can be estimated by σ = m 0.68 √ 2 (3) This method ensures that the local deviation is large when there are many large jumps between consecu- tive samples and smaller when this is not the case. 3 Singular Value Decomposition (SVD) 3.1 Introduction The singular value decomposition (SVD) is a generalization of the Eigen decomposition which can be used to analyze rectangular matrices (the Eigen-decomposition is defined only for squared matrix). By analogy with the Eigen decomposition, which decomposes an image into two simple matrix, the main idea of the SVD is to decompose a rectangular matrix as a product three matrix: Two orthogonal and one diagonal. The SVD is equivalent to principal component analysis (PCA) and is therefore an essential tool for multivariate analysis. 3.2 SVD Image Approximation The SVD uses Eigen decomposition of a positive semi-definite matrix in order to derive a similar decomposition applicable to all rectangular real number matrix. The main idea is to decompose any matrix into three matrix; two orthonormales and one diagonal. Formally, if A is a rectangular matrix, its SVD is written by: A = P∆ QT (4) 196 M.Moussa Jlassi, A. Douik, H. Messaoud P: the (normalized) eigenvectors of the matrix AAT (PPT = I). The columns of P are called the left singular vectors of A. Q: the (normalized) eigenvectors of the matrix AAT (QQT = I). The columns of Q are called the right singular vectors of A. ∆ the diagonal matrix of the singular values, ∆ = Λ 1 2 with Λ being the diagonal matrix of the Eigen values of matrix AAT and of the matrix AT A, since they are the same. A non-parametric background modeling technique has been applied on soccer video images. The main problem that can appear is the occurring of wrong detection pixels. Indeed the detection of moving objects as a shadows pixels allows to an over segmentation which will damage many works where this paper is registered. This algorithm is extremely important because it is a part of player’s classification and tracking [15] on a football scenes. SVD representation is very useful in image processing applications in particular for the spectral image compression [16]. The interest of SVD in this method is to determine number’s SVD of the treated image. Besides we will see the prominent contribution using SVD approach to restore and eliminate shadows, highlights and noise from camera displacement. In the developed background segmentation method described in this paper, the main objective is summarized by the use of the singular value decomposition. Let A is a given image represented by a matrix Ap = [ai j], which can be decomposed into a product of three matrix Uk Sk V Tk , where ai j is the appearance frequency of background pixel’s chromaticity and intensity; (p= red, green, blue). D. Valentin et al. [17] and H. Abdi et al. [18] prove the property’s importance to approximate a given matrix by SVD which will be substituted by another having reduced rank and dimension of each initial level from r to k (i.e. suppression of r-k column). The determined singular values for each level was presented in frequency space, their representation prove that for each one correspond a discrete frequency. The noise that can appear in the signal (in frequency space the amplitude of noise is constant) corresponds to a low amplitude, singular value whereas high amplitudes of these represents global signal energy. 3.3 Confidence intervals research This section presents the steps which allow to determine the singular values number for each level. – Image improvement : In this section, we describe the basic background model and the background subtraction process with singular value decomposition. The latter was used in both restoration, reconstruction of considred image, and increase the compactness distribution of different class, and also provide useful image information. – Weights Interpretation: To evaluate mathematical contribution of singular value decomposition, a quantification of global signal energy distribution according the weight of each singular value Skk was done. Figure 1 illustrate the energy distribution E defined by: E = k∑ i=1 A2i (5) The relative energy contained by each singular value K, noted pk is defined by: Pk = S2kk E (6) Where the energy of the K singular value is equal to S2kk. Objects Detection by Singular Value Decomposition Technique in Hybrid Color Space: Application to Football Images 197 Figure 1: Evaluation of energy according to singular values decomposition. As it is shown on the figures 2a, 2b and 2c, the choice of the image’s size which will be manipulated, is deduced from the curves representing standard deviation of each colour levels according to the singular value decomposition. In fact a good choice of singular value number leads to reduce both compactness in different distribution and computing time. Figure 2: Evaluation of standard deviation according to singular values of the red level. 198 M.Moussa Jlassi, A. Douik, H. Messaoud Figure 3: Evaluation of standard deviation according to singular values of the green level. Figure 4: Evaluation of standard deviation according to singular values of blue level. Figures 2a, 2b and 2c denote two zones, the first one defined in the interval [0, (Skkl)i where (Skkl)i is the singular value limits corresponding to the linear part of the curve i(red, blue, green), on this zone the curve prove a slope, beyond (Skkl)i a second zone appears where the standard deviation varied slightly, therefore the optimal singular value (Ŝkkl)i must necessarily belong to the first zone of each curve. Table 1 illustrates initial and improved standard deviations for three channels (RGB). – Choice of the singular values number: the choice of the singular values number, which will be kept, depends on two issues, the first one is the energy curve evaluated by figure 2 and the second is standard deviation curves of each chromatic level shown in figures 2a, 2b and 2c. In fact we specify for each component the limit singular value defined previously. Table 2 shows confidence intervals as well as singular value limits and the optimal value. Objects Detection by Singular Value Decomposition Technique in Hybrid Color Space: Application to Football Images 199 Table 1: Evaluation of improvement parameters. σ µ R 4.2044 119.610 G 4.7227 152.080 B 4.313 88.988 Rsvd 3.927 119.07 Gsvd 4.620 152.05 Bsvd 3 995 88.407 Table 2: Specification of confidence intervals. (Skkl)i (Ŝkk)i confidence intervals R 29 19 [0, 29] G 28 13 [0, 28] B 19 13 [0, 13] 4 Hybrid color space research by histogram analysis Many descriptors can be used in image processing field, C. Huang et al. [12] combine texture and color descriptors [19] to form hybrid visual feature index to retrieve natural color images, in fact this method is insensitive to image rotation and translation and then the experimental results show that the method achieves better performance than other recent relevant methods. The RGB space isn’t always the best one [20], Indeed, other colorimetric components, deduced from Red, Green and Blue, can be more suitable according to a considered case. Michael K. Ng et al. [13] consider restoring a single-color image from two degraded frames of the same scene by a RGB sensor and a luminance sensor. The RGB-to-YIQ transformation, the classical Tikhonov regularization and the Neumann boundary condition are used in the restoration process. R. Missaoui et al. [14] illustrate the superiority of an efficient content-based image mining and retrieval approach towards similarity analysis and retrieval effectiveness computation both in the use L* C* H* and CIECAM02 color spaces. In order to refine the result, a new effectiveness measure are proposed and experimented on an image, this approach consists to convert image from RGB space to other one which are grouped in Ψ set and select the suitable system which minimizes the overlapping between different clusters. where Ψ = (RRGB, GRGB, BRGB, rrgb, grgb, brgb, HHSL, SHSL, LHSL, XXY Z , YXY Z , ZXY Z , LLab, aLab, bLab, YY UV , UY UV , VY UV , CCMY , MCMY , YCMY , I1I1I2I3, I2I1I2I3, I3I1I2I3, AAC1C2, C1AC1C2, C2AC1C2, YY IQ, IY IQ, QY IQ, llch, clch, hlch, HHSV , SHSV , VHSV , YY CbCr, CbY CbCr, CrY CbCr, YY PbPr, PbY PbPr, PrY PbPr, YY DbDr, DbY DbDr, DrY DbDr), multidimensional space defined by a set of color levels frequently used. A new similarity measures which compare two color histograms and calculates the intersection coefficients, as illustrates in figure 3a and 3b. However Histogram analysis and conversion of image in various color space are an important tech- nique to achieve many studies in this field and lead to make decision about discrimination capacity of 200 M.Moussa Jlassi, A. Douik, H. Messaoud these levels thus determine a hybrid color space constituted by the three significant components. Algo- rithm 1 calculate similarity criterion between reference, and candidate image. a b Figure 5: (a) represents the intersection coefficient (0.041965) between reference level and bLab for player A. (b) represents the intersection coefficient (0.019788) between reference level and HHSL for player B. Algorithm 1: Read original image in gray level. Calculate Histogram Hg. For each level i Read the image in this level Calculate Histogram (Hp)i Estimate intersection between Hg and (Hp)i If inter ≈ 0 pi is a suitable plan Else Choose pi+1 End if End For. This algorithm is compiled for each player with various levels, the intersection coefficients between original (gray level) and converted frame were evaluated and given the following results: – Relevant levels for player A: HHSL, vLuv, I3 and I2, bLab, rrgb and brgb. – Relevant levels for player B: HHSL, I3, PrY PbPr, JPEGCrJPEGY CbCr, DrY DbDr, VY UV and C2Y C1C2. To appreciate and highlight the interest of this technique, we recapitulate results of some favorite levels in tables 3 and 4. This supervised training enables to control statistical parameters, confirm the efficient choice of this method and increase compactness power. Table 5 and 6 show the improvements introduced to the distribution of each different class. – For player A: Table 5 illustrates mean µ and standard deviation σ before and after segmentation, of original image (gray level) and represented image in each relevant level and the ratio of the standard deviation σ , before and after segmentation, by standard deviation of reference image. σre f be f (before) =15.232, σre f a f t (after) = 8.317. Objects Detection by Singular Value Decomposition Technique in Hybrid Color Space: Application to Football Images 201 Table 3: Significant levels for player A (PA). level inter 1 HHSL 0 2 vLuv 0 3 I3 0.00022401 4 I2 0.00029869 5 bLab 0.00171740 6 rrgb 0.03345300 7 brgb 0.04196500 – For player B: Similarly for player B and with the same way, segmentation parameters were given in table 6 and we conserve the same notation given for player A. Table 4: Significant levels for player B (PB). level inter 1 JPEGCrJPEGY CbCr 0 2 I3 0 3 HHSL 0.00067204 4 DrY DbDr 0.00238950 5 PrY PbPr 0.00418160 6 VY UV 0.01493400 7 C2Y C1C2 0.01978800 This technique contributes to research a suitable hybrid color space that is separate some distributions corresponding for each set pixels class by an iterative selection procedure. This procedure consists to extract the significant level from a set of color components according specified actors present in image. The obtained results show clearly how the use of color improves the segmentation quality. 5 Experimental results Using the probability Pr(xt) calculated in the equation (3), a pixel is considered as a foreground pixel if Pr(xt) < th. The threshold th is a global threshold over all the image that can be adjusted to achieve a de- sired percentage of false positives. Practically, this probability can be calculated in a very fast way using pre calculated lookup tables for the kernel function values given the intensity value difference,(Pi − pt), and the kernel function bandwidth. The detection of shadows as foreground pixels was a source of confusion with a background. The solution that allows to overcome this problem incorporates both sin- gular value decomposition to increase the compactness power of distributions and color information [21] where pixels intensities will be expressed. Indeed chrominance levels were better than these of lightness. They lead to discriminate foreground and their shadows. The work space where this segmentation was carried out is the Hrb constituted by HSL and rgb Previously determined. 202 M.Moussa Jlassi, A. Douik, H. Messaoud Table 5: Evaluation of parameters in favorite levels before and after segmentation (PA). σbe f Rapbe f σa f t Rapa f t HHSL 14.353 0.942 2.804 0.099 vLuv 3.873 0.254 2.480 0.087 I3 5.477 0.359 4.370 0.154 I2 5.831 0.382 7.424 0.262 bLab 6.082 0.399 5.624 0.198 rrgb 10.392 0.682 20.640 0.728 brgb 11.705 0.768 13.935 0.492 Table 6: Evaluation of parameters in favorite levels before and after segmentation (PB). σbe f Rapbe f σa f t Rapa f t JPEGCr 16.000 1.076 0.747 0.027 I3 5.385 0.362 4.502 0.164 HHSL 16.000 1.076 24.416 0.894 DrY DbDr 6.000 0.403 0.811 0.029 PrY PbPr 9.0554 0.609 0.765 0.028 VY UV 10.050 0.676 0.762 0.027 C2Y C1C2 10.724 0.721 0.760 0.027 Objects Detection by Singular Value Decomposition Technique in Hybrid Color Space: Application to Football Images 203 ! " # $ % & ' ( ) * Figure 6: (a, f) original images. (b, g), (c, h) present respectivly binary images before and after treatment. (d, i) segmented image with Hrb system. (e, j) output images in RGB system. 6 Conclusion In this paper, we present a non-parametric kernel density estimation technique, to model and subtract background which was developed in other color space more suitable instead the RGB space. Experimen- tal results has been improved by using an appropriate mathematical approach for objects detection and shadows suppression. This technique incorporates singular value decomposition to increase the compactness power of each distribution, also approximate a new image which will be manipulated on one hand, determine a suitable color space constituted by significant levels among set of levels commonly used in color image analysis based on a novel similarity measures for comparing color histogram of reference and candidate image where we calculate the intersection coefficient which present criterion’s discrimination on other hand. Also this technique proves that the gray levels and the RGB space not efficient for all applications. However the deduced color space (Hrb) allows to convincing results and confirm the efficiency of this method. Bibliography [1] A. Elgammal, R. Duraiswami, D. Harwood, and L. S. Davis, Background and Foreground Modeling Using Nonparametric Kernel Density Estimation for Visual Surveillance, Proc. IEEE 90(7), pp. 1151-1163, 2002. [2] Y. Ming, J. Jiang, J. Ming, Background Modeling and Subtraction Using a Local-Linear- Dependence-Based Cauchy Statistical Model, Proc. VIIth Digital Image Computing: Techniques and Applications, pp. 469-478, 2003. [3] O. Javed, K. Shafique, and M. Shah, A hierarchical approach to robust background subtraction using color and gradient information, In IEEE Workshop on Motion and Video Computing, 2002. [4] R. Agarwal and M. S. Santhanam, Digital watermarking in the singular vector domain, International Journal of Image and Graphics, Vol. 8, No. 3, pp. 351-368, 2008. [5] YL. Liu, J. Wang, X. Chen, A robust and fast non-local means algorithm for image denoising, Journal of Computer Science and Technology, 23(2): 270-279 Mar. 2008. [6] X. Zhang, K. Kobayashi, S. Saito and M. Nakajima, Reflectance-Field-Based Separation of Surface Reflection Components, Information and Media Technologies, Vol. 1, No. 2, pp.1040-1048, 2006. 204 M.Moussa Jlassi, A. Douik, H. Messaoud [7] M. Seki, T.F. Wada and H.Sumi, Background Subtraction Based on Cooccurrence of Image Varia- tions, In Computer Vision and Pattern Recognition, pp. 65-72, 2003. [8] T. Brox, M. Rousson, R. Deriche, and J.Weickert, Unsupervised segmentation incorporating colour texture and motion,Computer Analysis of Images and Patterns, volume 2756 of Lecture Notes in Computer Science, pp. 353-360, 2003. [9] O. Pujol and P. Radeva, Segmentation by Statistical Deformable Models, International Journal of Image and Graphics, Vol. 4, No. 3, pp. 433-452, 2004. [10] K. Verma and M. Hanmandlu, Color Segmentation via Improved Mountain Clustering Technique, International Journal of Image and Graphics, Vol. 7, No. 2, pp. 407-426, 2007. [11] A. Farhadi, M. Shahshahani, Image segmentation via local higher order statistics, International Journal of Imaging Systems and Technology, Vol. 13, No. 4, pp. 215-223, 2003. [12] C. Huang, J. Zhou and S. Yu, Color Image Retrieval Based on Color-Texture-Edge Feature His- tograms, International Journal of Image and Graphics, Vol. 6, No. 4, pp. 583-598, 2006. [13] Michael K. Ng and N. K. Bose, Fast color image restoration with multisensors, International jour- nal of imaging systems and technology, Vol. 12, No. 5, pp. 189-197, 2002. [14] R. Missaoui, M. Sarifuddin and J. Vaillancourt, Similarity measures for efficient content-based image retrieval, IEE Proceedings. Vision, Image, and Signal Processing, Vol. 152, No. 6, pp. 875- 887, 2005. [15] A. Colombari, A. Fusiello, V. Murino, Segmentation and tracking of multiple video objects, Pattern Recognition, pp. 1307-1317, 2007. [16] H. KOTERA, RGB to Pseudo-Spectral Image Conversion Using Spectral Palette and Compression by Singular Value Decomposition, NIHON GAZO GAKKAISHI, Vol. 42, pp. 215-223, 2003. [17] Abdi, H. (2003). Multivariate analysis. In M. Lewis-Beck, A. Bryman, and T. Futing (Eds): "Ency- clopedia for research methods for the social sciences". Thous and Oaks: Sage. [18] Abdi, H., Valentin, D. (2006). "Mathématiques pour les sciences cognitives (Mathematics for cog- nitive sciences)". Grenoble: PUG. [19] H. Matsuda, S. Kubota and H. Sato, Comparison of Hair Color Using Image Analysis, Japanese Journal of Forensic Science and Technology, Vol. 13, No. 2, pp. 151-166, 2008. [20] M. Rousson, T. Brox, and R. Deriche, Active unsupervised texture segmentation on a diffusion based feature space, In Proc. IEEE Computer Society Conf. on Computer Vision and Pattern Recog- nition, vol. 2, pp. 699-704, June 2003. [21] M. G. Linguraru, M. Á. G. Ballester, N. Ayache. Deformable Atlases for the Segmentation of Internal Brain Nuclei in Magnetic Resonance Imaging, International Journal of Computers, Com- munications and Control, Vol. II, No. 1, pp. 26-36, 2007.