# Sparsity Based Locality-Sensitive Discriminative Dictionary Learning for Video Semantic Analysis

Authors: Ben-Bright Benuwa; Yongzhao Zhan; Benjamin Ghansah; Ernest K. Ansah; Andriana Sarkodie
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Dictionary learning (DL) and sparse representation (SR) based classifiers have greatly impacted the classification performance and have had good recognition rate on image data. In video semantic analysis (VSA), the local structure of video data contains more vital discriminative information needed for classification. However, this has not been fully exploited by the current DL based approaches. Besides, similar coding findings are not being realized from video features with the same video category. Based on the issues stated afore, a novel learning algorithm, called sparsity based locality-sensitive discriminative dictionary learning (SLSDDL) for VSA is proposed in this paper. In the proposed algorithm, a discriminant loss function for the category based on sparse coding of the sparse coefficients is introduced into structure of locality-sensitive dictionary learning (LSDL) algorithm. Finally, the sparse coefficients for the testing video feature sample are solved by the optimized method of SLSDDL and the classification result for video semantic is obtained by minimizing the error between the original and reconstructed samples. The experiment results show that the proposed SLSDDL significantly improves the performance of video semantic detection compared with the comparative state-of-the-art approaches. Moreover, the robustness to various diverse environments in video is also demonstrated, which proves the universality of the novel approach.


---

## Body

## 1. Introduction

SR is an active research hotspot, particularly its application for signal reconstruction [1], and it performs well with video analysis and image classification based on experimental outcomes discussed in [2, 3]. DL on the other hand is to learn a good dictionary from training samples so that a given signal could be well represented; hence the quality of the dictionary is very crucial for efficient SR [4]. The dictionary could be determined by either using all the training samples as the dictionary to code the test samples (e.g., locality-constrained linear coding (LLC) in [5]) or adopting a learned dictionary for the sparse representation for each training sample in the set (e.g., KSVD in [6], Fisher discriminative dictionary learning (FDDL) [7]). Besides, group-centered sparse coding likened to rank minimization problem is used to measure the sparse coefficient of each group by estimating the values of each grouping in [8]. All the methods that adopt the first strategy use training samples as the dictionary. Although they show good classification performance the dictionary might not be effective enough to represent the samples well because of noisy information that could have accompanied the original training samples and it may not also wholly exploit the discrimination information hidden in the training samples. The second category is also not suitable for recognition because it only requires that the dictionary is best expressed in the training samples with strict sparse representation. The above stated issues were addressed by the LSDL approach that incorporated a locality constraint into the objective function of the DL which ensures that overcomplete dictionary learned is more representative. The problem with the traditional sparse representation methods is that they cannot produce the same or similar results when the input features are from the same categorization.The elementary approach to building the dictionary is by exhausting all the training samples which may result in the size of the dictionary being huge and is subsequently unfavorable to the sparse solver in [9]. A lot of techniques such as the Method of Optimal Direction (MOD) in [10] which updates all the atoms simultaneously with fixed sparse codes using least-square methods and an orthogonal matching pursuit for sparse coding, the K-SVD algorithm in [11] for learning a handful sized dictionary for sparse coding from the training data have recently been proposed. An attempt was made to resolve this issue by further iteratively updating the KSVD (which focuses on only the representational power or efficiency of the dictionary as discussed in [12], but not its discrimination abilities) trained dictionary grounded on the result of a linear classifier, by obtaining a dictionary that may be good for classification with representational power. Other efforts along similar direction include [13, 14], which use more sophisticated objective functions in dictionary optimization for the training phase so as to gain some discriminative power for the dictionary. The other discriminative dictionary learning method uses discriminative and reconstructive error to learn the dictionary. A structured based Fisher Discriminative Dictionary Learning (FDDL) was proposed in [15]. The approach improves the performance of pattern classification whose dictionary has a relation with the class labels and further exploited the discriminability in both representative coefficient and its residual in [16]. Recently a discriminative structured dictionary learning with hierarchical group sparsity that reduces the linear predictive error and discriminability of sparse codes using hierarchical group sparsity was introduced in [17]. A discriminative structured dictionary learning for image classification that combines into the objective function, the discriminative properties of the reconstruction error, representative error, and the classification error terms was also proposed in [18]. In the same vein of improving the discriminability of dictionary learning algorithms, [19] proposed the structure adaptive dictionary leaning for sparse representation based classification, [20] proposed the learning of dictionary discriminatively for group sparse representation, and discriminative dictionary learning for face recognition with low ranked regularization was also introduced in [21]. The locality-constrained linear coding for image classification (LLC) built on the theories of linear spatial pyramid matching using sparse coding for image classification [22] was proposed in [5]. LLC could achieve a smaller reconstruction error with multiple code reconstruction and local smoothness with respect to sparsity.More recently, there has been an advancement in sparse dictionary learning for video semantic as proposed in [2], a video semantic detection method based on locality-sensitive discriminant sparse representation and weighted KNN (LSDSR-WKNN), to have better category discrimination on the sparse representation of video semantic concepts. Despite having better category discrimination on the SR of video semantic concepts, the LSDSR-WKNN technique failed to fully exploit the potential information of the samples. A latent label consistent DL (LLCDL) that solves a unified framework that minimizes, simultaneously, the structured discrimination sparse codes approximation, the classification error, and the structured sparse reconstruction to boost representation and classification performances was proposed in [23]. The authors of LLCDL algorithm previously introduced the joint label consistence embedded and dictionary learning (JEDL) algorithm [24] based on LC-KSVD. The technique concurrently learns discriminative sparse codes, sparse reconstruction, classification errors, and code approximation that enable linear combination of signals for the sparse code autoextractor with sparse codes during classification. More so, vital similarity information of signals is achieved by enforcing sparse coefficients to be discriminative among different classes. However, it implemented the KSVD computation approach to obtain the dictionary columns which renders it computationally expensive. All the above SR for DL techniques demonstrates an outstanding efficient performance, but are still faced with multiplicity of scene tolerance issues, in enhancing the accuracy of video semantic analysis further.Based on the aforementioned, this paper seeks to enhance the power of discrimination of sparse representation features by encoding group sparse codes of samples from the same category and thus proposes a sparsity based locality-sensitive discriminative dictionary learning for (SLSDDL) for VSA, which is more efficient and has superior numeric stability. The SLSDDL algorithm enables the adjustment of the dictionary adaptively using the differences between the reconstructed dictionary atoms and the training samples with the locality adaptor. More so, the implementation of the locality adaptor at both DL and sparse coding stages increases the efficiency of the algorithm of the locality and similarity of the dictionary atoms. The dictionary information could also be exploited by the proposed algorithm with the introduction of a discriminant loss function during the dictionary learning stage, to obtain more discriminative information and enhance the classification ability of spares representation features. The dictionaries learned could realistically represent video semantic more and thus give a better representation of the samples belonging to the sparse coefficients.The main contributions of this paper are as enumerated as follows:(1)
A discriminative loss function is utilized, giving an optimal dictionary for addressing sparse representation issues and optimized sparse coefficients for reconstructing the dictionary, so as to enhance the discriminative classification of sparse representation features.(2)
The introduction of the group sparsity also enables efficient reconstruction of samples most especially when the size gets large.(3)
A locality-sensitive discriminative dictionary learning and sparse representation based on group sparsity is developed for video semantic detection that encodes video features originally. Thus features are sparsely encoded with video semantic detection for better preservation of the dictionary, hence an improvement in the accuracy of video concept detection.The rest of the paper is organized into the following sections: Section2 presents a review of related works; Section 3 discusses the proposed algorithms; experimental results are presented in Section 4. Finally, Section 5 outlines the main conclusions and recommendations.


## 2. Related Works

### 2.1. Sparse Representation Algorithms

SR for signal acquirement and the overall techniques included coding, sampling, compression, transmission, and decoding and is one of the utmost essential ideologies in the field of signal processing theorem which tells us that a signal that has been sampled can be impeccably reconstructed from an arrangement of samples if the sampling rate surpasses twice the maximum frequency of the original signal [25]. It utilizes an overcomplete dictionary to linearly reconstruct a data case for a given dictionary. Suppose that the example is from space Rd, and thus all the examples concatenated to form a matrix, denoted as XєRdxm. If any sample can be approximately represented by a linear amalgamation of dictionary D and the number of the samples is larger than the dimension of samples inD, i.e.,m>d, dictionary D is referred to as an overcomplete dictionary. A signal is said to be compressible if it is a sparse signal in the original or transformed domain when there is no information or energy loss during the course of transformation. Generally, from the matrix stated above, if d<m, and y єRd then we define the linear system of equations as(1)y=ZβThe sparsest representation solution can be acquired by solving (1) with the l0-norm minimization constraint [26]. Thus problem (1) can be converted to the following optimization problem:(2)β^=argminβ0s.t.y=Zβ.Problem (2) is called the k-sparse approximation problem. Because real data always contains noise, representation noise is unavoidable in most cases. Thus the original model (1) can be revised to a modified model with respect to small possible noise by denoting(3)y=Zβ+s,where sϵRd refers to representation noise and is bounded as s2≤ε. With the presence of noise, the sparse solutions of problems (2) can be approximately obtained by resolving the following optimization problems:(4)β^=argminβ0s.t.y-Zβ22≤ε.Or(5)β^=argminy-Zβ22s.t.β0≤ε.Furthermore, according to the Lagrange multiplier theorem, a proper constant λ exists such that (4) and (5) are equivalent to the following unconstrained minimization problem with a proper value of λ.(6)β^=Lβ,λ=argminy-Zβ22+λβ0,where λ refers to the Lagrange multiplier associated with β0.


### 2.2. Locality-Sensitive Sparse Representation

Test examples in SR are usually represented by the dictionary atoms that may actually not be neighboring it for signal or data reconstructions. This may render it incongruous for holding data locality and hence could lead to poor recognition rates. In the LSDL method, the locality constraints of data locality were added in the phase of the dictionary learning and sparse coding, so that the test sample can be well represented by the neighboring dictionary atoms. The optimized function for LSDL is stated as follows:(7)minD,XA-DXF2+λ∑i=1NPiΘxi22,(8)s.t.1Txi=1∀i=1,…,Nwhere piϵRKx1 is locality adapter and λ is the scalar parameters which measures the locality constraint. The LSDL method does not consider the class information, and therefore we design the discriminating loss function using class information to enhance the sparse representation based classification, in order to improve the accuracy of image data representation or video analysis.


## 2.1. Sparse Representation Algorithms

SR for signal acquirement and the overall techniques included coding, sampling, compression, transmission, and decoding and is one of the utmost essential ideologies in the field of signal processing theorem which tells us that a signal that has been sampled can be impeccably reconstructed from an arrangement of samples if the sampling rate surpasses twice the maximum frequency of the original signal [25]. It utilizes an overcomplete dictionary to linearly reconstruct a data case for a given dictionary. Suppose that the example is from space Rd, and thus all the examples concatenated to form a matrix, denoted as XєRdxm. If any sample can be approximately represented by a linear amalgamation of dictionary D and the number of the samples is larger than the dimension of samples inD, i.e.,m>d, dictionary D is referred to as an overcomplete dictionary. A signal is said to be compressible if it is a sparse signal in the original or transformed domain when there is no information or energy loss during the course of transformation. Generally, from the matrix stated above, if d<m, and y єRd then we define the linear system of equations as(1)y=ZβThe sparsest representation solution can be acquired by solving (1) with the l0-norm minimization constraint [26]. Thus problem (1) can be converted to the following optimization problem:(2)β^=argminβ0s.t.y=Zβ.Problem (2) is called the k-sparse approximation problem. Because real data always contains noise, representation noise is unavoidable in most cases. Thus the original model (1) can be revised to a modified model with respect to small possible noise by denoting(3)y=Zβ+s,where sϵRd refers to representation noise and is bounded as s2≤ε. With the presence of noise, the sparse solutions of problems (2) can be approximately obtained by resolving the following optimization problems:(4)β^=argminβ0s.t.y-Zβ22≤ε.Or(5)β^=argminy-Zβ22s.t.β0≤ε.Furthermore, according to the Lagrange multiplier theorem, a proper constant λ exists such that (4) and (5) are equivalent to the following unconstrained minimization problem with a proper value of λ.(6)β^=Lβ,λ=argminy-Zβ22+λβ0,where λ refers to the Lagrange multiplier associated with β0.


## 2.2. Locality-Sensitive Sparse Representation

Test examples in SR are usually represented by the dictionary atoms that may actually not be neighboring it for signal or data reconstructions. This may render it incongruous for holding data locality and hence could lead to poor recognition rates. In the LSDL method, the locality constraints of data locality were added in the phase of the dictionary learning and sparse coding, so that the test sample can be well represented by the neighboring dictionary atoms. The optimized function for LSDL is stated as follows:(7)minD,XA-DXF2+λ∑i=1NPiΘxi22,(8)s.t.1Txi=1∀i=1,…,Nwhere piϵRKx1 is locality adapter and λ is the scalar parameters which measures the locality constraint. The LSDL method does not consider the class information, and therefore we design the discriminating loss function using class information to enhance the sparse representation based classification, in order to improve the accuracy of image data representation or video analysis.


## 3. Proposed Method

The proposed algorithm for SLSDDL is based on the locality-sensitive adaptor, and a discriminative lost function centered on group SR is incorporating into the objective function of locality-sensitive discriminative dictionary learning method as stated in (7) and detailed as explained below. The proposed method could achieve optimal dictionary and further enhance the power of discriminability of sparse codes as well as computational cost. As a result, features from representation coefficient might not be capable of achieving the same coding results; hence the assumption is made that samples should be encoded as similar sparse coefficients in the SR based data detection with the objective of enhancing the power of discrimination in SR based classifiers.Assume thatA=a1,a2,…,an=A1,A2,…,AkϵRdxn denotes n training samples from k classes where the column vector a1 is the sample ii=1,…,n, and submatrix Aj consists of column vectors from class jj=1,…,k. If there are M atoms in the dictionary D=D1,D2,…,DMϵRdxM, an overcomplete dictionary for SR with M≤n, then coding coefficients of A over D could be denoted by X=x1,x2,…,xLϵRMxn. Now considering image or video features of the same category of the representation coefficient or the representation solution with class information, which is very imperative for classification, our SLSDDL framework is modeled as follows:(9)minD,XAij-DXF2+λN2PijΘxij22+gxij,(10)s.t.1Txij=1∀i=1,…,Nwhere we have the locality adaptor as PϵRKx1, AϵRdxn is the training sample, DϵRdxM is the dictionary, xiϵRMx1 is the sparse coefficient vector, and the discriminative lost function for group sparsity is gxij. Here the locality adaptor Pij uses the l2-norm function and its kth element in Pij is given by Pijj=aij-dij and symbol Θ represents element-wise multiplication, gxij is the proposed discriminant loss function to enforce group sparsity discriminability as defined in (11) below, the shift variant constant 1Txij enforces the coding result of x to remain the same although the origin of the data coordinate may be shifted as indicated in [27], and the regularization parameter controlling the reconstruction error and the sparsity is λ.Bearing in mind cases where sample features from the same category could be having similar sparse codes, we propose a discriminant loss function based on a group sparse coding of the sparse coefficients for the purposes of enhancing the power of discrimination of input signals or samples in SR. The group structure enforced on the coefficient vector ensures that the variables in the same group tend to be either zero or nonzero simultaneously and thus enhances classification, hence better classification results. Consequently, samples from same category are compacted and the ones from different categories are separated. The discriminant loss function,gxij, based on sparse coefficients is explained as follows:(11)gxij=1-1Njxij-1Nj∑lϵ1,NjΛl≠ixij22+xij22,where 1-1/Njxij-1/Nj∑lϵ1,NjΛl≠ixij22+xij22 is the within class-similar term enforcing group sparsity by computing the representations whose nonzero coefficients are further divided into groups, Nj is the number of samples of the representation coefficient xij belonging to the class j, and N is the number of training samples. The term xij22 combined with X22 could make (9) more stable based on theorem of [28]. It is worth noting that group sparsity is enforced in the way xij is calculated. The encoding of xij using the proposed method significantly is computationally less expensive, compared with the existing SR classification approaches as a result of the smaller dictionary size. Thus xij is much more easier to obtain than xi, and it enforces the capture of dependencies among video samples of the same categorization. With η set to 1 for simplicity, (9) can be reformulated as(12)minD,XAij-DXF2+λ1∑i=1NPijΘxij22+λ21-1Njxij-1Nj∑lϵ1,NjΛl≠ixij22+xij22.(13)s.t.1Txij=1∀i=1,…,NThe proposed method as stated equation (12) is implemented by enforcing data locality with the locality adaptor being used to measure the distance between the test sample y and each column of D. Note that D=D1,D2,…,DM represents all the training samples in the feature space. The vector P, the dissimilarity vector in (12) is implemented to suppress the corresponding weight and also penalizes the distance between the test and each training samples in the feature space. Furthermore, it should however be made known that the resulting coefficients in our SLSDDL formulation may not be fully sparse with regard to l2 – norm, but is seen as sparse because the representation solutions only have few significant values with most being zero. The test samples and their neighboring training samples in feature space are encoded when the problem of (11) is being minimized and the resulting coefficients X still are sparse because as Pijj gets large, xijj shrink to be zero. Hence most coefficients get zero with just some few having significant values.


### 3.1. Optimization

The objective function in (12) could be divided into two subproblems by updating X with D fixed and updating D with X fixed since it is not convex as a whole. To find the desired dictionary D and the sparse coefficient X, an alternative optimization is implemented iteratively adopting the theories of [15, 23, 24, 29].Updating X with D Fixed, Sparse Coding Stage. When the coefficient matrix X is being updated with the dictionary D being fixed, the objection function of (12) is reduced to the coding problem below:(14)X=minXAij-DXF2+λ1∑i=1NPijΘxij22+λ2∑i=1Ngxi.X in (15) could be addressed on class bases. Thus xij corresponding to class i could be derived as follows:(15)xij=minxijAij-Dxij22+λ1∑i=1NPijΘxij22+λ21-1Njxij-1Nj∑lϵ1,NjΛl≠ixij22+xij22.(16)s.t.1Txij=1Equation (15) can be rewritten by adopting Lagrange function L(xij⁡,μ) as follows:(17)Lxi,μ=Ai-Dxi22+λ1∑i=1NPijΘxij22+λ21-1Njxij-1Nj∑lϵ1,NjΛl≠ixij22+xij22+μ1Txij-1.Equation (18) can be converted as follows:(18)Lxij,μ=xijTCxi+λ1xijTdiag⁡Pij2xij+λ2xijTYxij+xijTIxij+μ1Txij-1,where C=aij1T-DTaij1T-D, diag⁡Pij2 is a diagonal matrix whose nonzero elements are the square of the entries of Pij, Y=(I-1/NjI-1/Nj∑lϵ1,NjΛl≠ixijxij1TTI-1/NjI-1/Nj∑lϵ1,NjΛl≠ixijxij1T.Let∂L(xij⁡,μ)/∂xij=0.We have(19)θxij+μ1=0,where θ=2C+λ1diag⁡Pij2+λ2Y+1; once (20) is premultiplied by 1Tθ-1, we get μ=-1Tθ-11-1. Then through substituting μ into (19), the analytical solution of (17) is obtained as(20)xi~=C+λ1diag⁡Pij2+λ2Y+1-11.Furthermore, the normalized xij of xij~ is given as(21)xij=xij~1Txij~Updating D with the Sparse Coefficient Matrix X Fixed, the Dictionary Updates Stage. During the dictionary update stage, the objective function in (12) is reduced to (22) as stated below:(22)D=minD⁡A-DXF2+λ1∑i=1NPijΘxij22+λ2∑i=1Ngxij.LettingFD=minD⁡A-DXF2+λ1∑i=1N||PijΘxij||22+λ2∑i=1Ngxi, we take the partial derivatives of FDwith respect to dk for k=1,2…K, which gives(23)∂F∂dk=∑I=1N-2xikjaij-Dxij-2λ1xikj2xij-dkjΘ∂dkj∂dk.Letting∂F/∂dk=0, and γ=∂dkj/∂dk, we obtain UDT=V, where the matrices U∈RKxK and V∈RKxm are as detailed below:(24)U=∑i=1N1+λ1γij1xij12xi1jxi2j⋯xi1jxiKjxi1jxi2j1+λ1γij1xij22⋯xi2jxiKj⋮⋮⋱⋮xi1jxiKjxi2jxiKj⋯1+λ1γij1xijK2.(25)V=∑i=1Nxi1j1+λ1xi1jaijTxi2j1+λ1xi2jaijT⋮xiKj1+λ1xiKjaijT.The optimal X and D could be gotten by alternating between sparse coding and dictionary learning until an optimal iteration, or error of reconstruction less than a threshold value is gotten. The algorithm for SLSDDL is summarized in Algorithm1. As an extension of the LSDL method, the proposed SLSDDL method seeks to obtain discriminative information of all training samples. Therefore, the LSDL method is espoused to initialize the sparse coefficients of all the training samples.Algorithm 1:Sparsity Locality–Sensitive Discriminative Dictionary Learning Algorithm.
Input: Training samples A, Initial dictionary D and parametersλ1,λ2 Output: The learned dictionary D (a) Initialize the coding coefficient matrix X and i i←1 (b) Optimize the solution by updating the sparse coding matrix X and the dictionary D. Update X by fixing D and updating each x i = i = 1 , … , k according to equation (22) on class bases by solving for xij and then do X′(:,i)←xij (c) If i=N, update X, which means X←X′else do i=i+1 and go to (b) (d) Initialize k1 and k2 respectively with k1←1 and k2←1 (e) Solve equation (24) for the solution of U(k1,k2) (f) Go to (g) if k2=K else do k2=k2+1 and return to (e) (g) Compute V(k1,:) from equation (25) (h) Fix X and update D using equation (22) (i) If k2=K, execute D′=(U/V)T and go to (j) otherwise execute k1←k1+1, k2←1 and return to (e) (j) Compute the reconstruction error. If the error value is less than the current minimum values, update the dictionary D′′ on the minimum error which is D′′←D′. (k) Iteratively return to step (b) until convergence or the reconstruction error is less than the threshold error, update D and the algorithm ends or go to (a)


### 3.2. Classification Scheme

For a given test sample y, the representation coefficients on dictionary D are given as follows:(26)x=arg⁡minx⁡y-Dx22+λPijΘxij22.The test sample can finally be classified after obtainingD, where λ is a scalar constant that measures sparsity, Θ represents element-wise multiplicative symbol, p=p1,p2,…,pkT, and every entry is represented pk=y-dk2. We utilized the Lagrange multiplier to obtain the solution for (28) as explained below:(27)Lx,μ=minx⁡y-Dx22+λPijΘxij22+μ1Txij-1.Equation (27) is easily simplified as(28)Lx,μ=xTC′xi+λxTdiag⁡P2x+μ1Tx-1,whereC′=y1T-DTy1T-D.Let∂Lx,μ/∂x=0, which gives us(29)θx+μ1=0,where θ=2C′+λdiag⁡P2; once (29) is premultiplied by 1Tθ-1, we get μ=-(1Tθ-11)-1. Then through substituting μ into (30), the analytical solution of (30), x~, is obtained as(30)x~=C+λdiag⁡P2+-11.Sparse coding coefficient x is the then obtained by normalizing x~ and is determined as(31)x=x~1Tx~Using the analysis in [30], we get the sparse coding efficient associated with test sample y by solving (30) and (31), after which the residual rjy=||y-Dixi||22 is calculated, where xi is the sparse coding coefficient on theith class and the test sample y is finally classified into the class that has the minimum residual as formulated below:(32)classy=arg⁡minj⁡rjy.


## 3.1. Optimization

The objective function in (12) could be divided into two subproblems by updating X with D fixed and updating D with X fixed since it is not convex as a whole. To find the desired dictionary D and the sparse coefficient X, an alternative optimization is implemented iteratively adopting the theories of [15, 23, 24, 29].Updating X with D Fixed, Sparse Coding Stage. When the coefficient matrix X is being updated with the dictionary D being fixed, the objection function of (12) is reduced to the coding problem below:(14)X=minXAij-DXF2+λ1∑i=1NPijΘxij22+λ2∑i=1Ngxi.X in (15) could be addressed on class bases. Thus xij corresponding to class i could be derived as follows:(15)xij=minxijAij-Dxij22+λ1∑i=1NPijΘxij22+λ21-1Njxij-1Nj∑lϵ1,NjΛl≠ixij22+xij22.(16)s.t.1Txij=1Equation (15) can be rewritten by adopting Lagrange function L(xij⁡,μ) as follows:(17)Lxi,μ=Ai-Dxi22+λ1∑i=1NPijΘxij22+λ21-1Njxij-1Nj∑lϵ1,NjΛl≠ixij22+xij22+μ1Txij-1.Equation (18) can be converted as follows:(18)Lxij,μ=xijTCxi+λ1xijTdiag⁡Pij2xij+λ2xijTYxij+xijTIxij+μ1Txij-1,where C=aij1T-DTaij1T-D, diag⁡Pij2 is a diagonal matrix whose nonzero elements are the square of the entries of Pij, Y=(I-1/NjI-1/Nj∑lϵ1,NjΛl≠ixijxij1TTI-1/NjI-1/Nj∑lϵ1,NjΛl≠ixijxij1T.Let∂L(xij⁡,μ)/∂xij=0.We have(19)θxij+μ1=0,where θ=2C+λ1diag⁡Pij2+λ2Y+1; once (20) is premultiplied by 1Tθ-1, we get μ=-1Tθ-11-1. Then through substituting μ into (19), the analytical solution of (17) is obtained as(20)xi~=C+λ1diag⁡Pij2+λ2Y+1-11.Furthermore, the normalized xij of xij~ is given as(21)xij=xij~1Txij~Updating D with the Sparse Coefficient Matrix X Fixed, the Dictionary Updates Stage. During the dictionary update stage, the objective function in (12) is reduced to (22) as stated below:(22)D=minD⁡A-DXF2+λ1∑i=1NPijΘxij22+λ2∑i=1Ngxij.LettingFD=minD⁡A-DXF2+λ1∑i=1N||PijΘxij||22+λ2∑i=1Ngxi, we take the partial derivatives of FDwith respect to dk for k=1,2…K, which gives(23)∂F∂dk=∑I=1N-2xikjaij-Dxij-2λ1xikj2xij-dkjΘ∂dkj∂dk.Letting∂F/∂dk=0, and γ=∂dkj/∂dk, we obtain UDT=V, where the matrices U∈RKxK and V∈RKxm are as detailed below:(24)U=∑i=1N1+λ1γij1xij12xi1jxi2j⋯xi1jxiKjxi1jxi2j1+λ1γij1xij22⋯xi2jxiKj⋮⋮⋱⋮xi1jxiKjxi2jxiKj⋯1+λ1γij1xijK2.(25)V=∑i=1Nxi1j1+λ1xi1jaijTxi2j1+λ1xi2jaijT⋮xiKj1+λ1xiKjaijT.The optimal X and D could be gotten by alternating between sparse coding and dictionary learning until an optimal iteration, or error of reconstruction less than a threshold value is gotten. The algorithm for SLSDDL is summarized in Algorithm1. As an extension of the LSDL method, the proposed SLSDDL method seeks to obtain discriminative information of all training samples. Therefore, the LSDL method is espoused to initialize the sparse coefficients of all the training samples.Algorithm 1:Sparsity Locality–Sensitive Discriminative Dictionary Learning Algorithm.
Input: Training samples A, Initial dictionary D and parametersλ1,λ2 Output: The learned dictionary D (a) Initialize the coding coefficient matrix X and i i←1 (b) Optimize the solution by updating the sparse coding matrix X and the dictionary D. Update X by fixing D and updating each x i = i = 1 , … , k according to equation (22) on class bases by solving for xij and then do X′(:,i)←xij (c) If i=N, update X, which means X←X′else do i=i+1 and go to (b) (d) Initialize k1 and k2 respectively with k1←1 and k2←1 (e) Solve equation (24) for the solution of U(k1,k2) (f) Go to (g) if k2=K else do k2=k2+1 and return to (e) (g) Compute V(k1,:) from equation (25) (h) Fix X and update D using equation (22) (i) If k2=K, execute D′=(U/V)T and go to (j) otherwise execute k1←k1+1, k2←1 and return to (e) (j) Compute the reconstruction error. If the error value is less than the current minimum values, update the dictionary D′′ on the minimum error which is D′′←D′. (k) Iteratively return to step (b) until convergence or the reconstruction error is less than the threshold error, update D and the algorithm ends or go to (a)


## 3.2. Classification Scheme

For a given test sample y, the representation coefficients on dictionary D are given as follows:(26)x=arg⁡minx⁡y-Dx22+λPijΘxij22.The test sample can finally be classified after obtainingD, where λ is a scalar constant that measures sparsity, Θ represents element-wise multiplicative symbol, p=p1,p2,…,pkT, and every entry is represented pk=y-dk2. We utilized the Lagrange multiplier to obtain the solution for (28) as explained below:(27)Lx,μ=minx⁡y-Dx22+λPijΘxij22+μ1Txij-1.Equation (27) is easily simplified as(28)Lx,μ=xTC′xi+λxTdiag⁡P2x+μ1Tx-1,whereC′=y1T-DTy1T-D.Let∂Lx,μ/∂x=0, which gives us(29)θx+μ1=0,where θ=2C′+λdiag⁡P2; once (29) is premultiplied by 1Tθ-1, we get μ=-(1Tθ-11)-1. Then through substituting μ into (30), the analytical solution of (30), x~, is obtained as(30)x~=C+λdiag⁡P2+-11.Sparse coding coefficient x is the then obtained by normalizing x~ and is determined as(31)x=x~1Tx~Using the analysis in [30], we get the sparse coding efficient associated with test sample y by solving (30) and (31), after which the residual rjy=||y-Dixi||22 is calculated, where xi is the sparse coding coefficient on theith class and the test sample y is finally classified into the class that has the minimum residual as formulated below:(32)classy=arg⁡minj⁡rjy.


## 4. Experimental Results and Analysis

This section details the experimental results and their analysis to demonstrate the effectiveness of the proposed method.


### 4.1. Video Shot Preprocessing

In the experiments, ordered samples clustering centered on artificial immune in [31] was adopted to extract the static image frames from each original video data utilizing the video key-frame extraction approach. Afterwards, features consisting of the 5-dimensional radial Tchebichef moment [32], 6-dimensional gray level cooccurrence matrix (GLCM) [33], 81-dimensional HSV color histogram [34], and 30-dimensional multiscale local binary pattern (LBP) [35] from the key-frame were extracted. The details of these features could be referred to in [2]. Figure 1 shows some key-frames of the three video datasets implemented.Figure 1
Some key frames from video shots for the respective datasets.
(a)
Some key frames from OV video set (b)
Part key frames from the TRECVID 2012 video set (c)
Part key frames from the YouTube video set


### 4.2. Database Selection and Video Analysis

Experiments are performed on natural images to demonstrate the efficient performance of our methods in this section. We analyze and compare the performance of our proposed algorithm with most typical algorithms such as the KSVD [11], FDDL, LLC [5], and LSDL [3] algorithms. Out of the many collections of datasets for video categorization and classification, three of them are being used in our experimental setup or evaluations. The public datasets being used are the TRECVID 2012 video dataset, OV video dataset, and YouTube video dataset.The TRECVID 2012 videos dataset has airplane, baby, building, car, dog, flower, instrumental_musician, mountain, scene_text, and speech as its video semantic models with each class containing 60 data sample; 50 of the samples were randomly as training samples, and the remaining as test samples.The YouTube video dataset iscomprised of basketball, biking, diving, golf_swing, horse_riding, soccer_juggling, swing, tennis, trampoline_jumping, volleyball, and walking as semantic videos with each class containing 70 data samples, out of which 60 were randomly selected as training samples, and the rest as test samples, and the semantic concepts ofthe OV dataset contain aircraft, sea, rocket, parachute, road, face, satellite, and star. Each class consists of 70 samples. For each class, 60 samples are randomly selected as training samples, and the remaining ones are testing samples. The proposed approach considered the L2 norm locality adaptor. The experimental results were realized by twentyfold cross-validation in which training samples are selected randomly and the remaining as the testing samples from the various video datasets.


### 4.3. Parameter Selection

Several parameters includingλ, the classification parameter, λ1, a positive weighing parameter for the locality-sensitive constraint, and λ2 for the discriminative constraint were utilized by the proposed SLSDDL and the classification error scheme, with varied values assigned depending on the dataset being used. More so, the classification parameter, λ, made a little or no effect on the output of the experimental results and hence was set to 0.01 in all experiments. The recognition rates of the proposed SLSDDL approach (for the optimization phase) with varying values of λ1 and λ2 on TRECVID dataset are as depicted by Figure 2. It could be seen from the figure that the optimum results were obtained for recognition when λ1 is 0.01 and λ2 is 0.007, respectively, with λ2 and λ1 values being fixed for each dataset by twentyfold cross validation. It is worth noting that different parameter values were realized for the experiment on the respective datasets because of the varying fundamental structure of the datasets. Based on the values stated in Table 1, an experiment was conducted to validate the performance of our proposed.Table 1
Parameter values implemented on the various data sets.
Dataset Parameter Values used λ 1 λ 2 TRECVID 2012 0.007 0.01 OV 0.006 0.03 YOUTUBE 0.5 0.01 Table1   indicates the various parameter selections with their respective datasets. Based on the aforementioned values, an experiment was conducted to validate the performance of our proposed algorithms and the findings are detailed below. Different datasets have different parameter settings because the structure of each dataset differs and hence the different parameter values.Figure 2
Recognition rate Vrs Variations of parameter values on TRECVID Dataset.


### 4.4. Experimental Results and Analysis: TRECVID 2012 Video Dataset

The recognition rates of video semantic detection of the proposed SLSDDL with varying video features for the initial dictionaries are as indicated in Table2. It could be seen that the SLSDDL gives an optimum performance when the size of the dictionary is 122 x 400 and thus resulted in the highest accuracy of semantic analysis and hence is chosen.Table 2
Classification results on different dictionary atoms of TRECVID 2012.
Number of the dictionary atoms 10 20 30 40 50 Accuracy Rate (%) 62 72.7 77.1 84.83 82.6The recognition rates of LLC, FDDL, LSDL, KSVD, and SLSDDL are as shown in Table3. It could be seen that the proposed SLSDDL comparatively obtained the highest recognition rates than the other recognition approaches. As indicated by Figure 3, the average recognition rates of various video semantic detection methods associated with each class on the TRECVID video dataset are also presented, which clearly suggests that the proposed method is best among all the comparative approaches on most categories. The recognition rate of the proposed method on the TRECVID dataset for instance outperformed KSVD by 8.23% and 7.86% against LSDL which confirms the effectiveness of the proposed method. Hence, the proposed SLSDDL approach could effectively improve best the accuracy rates of TRECVID video semantic feature detections. Nevertheless, the recognition rates for the proposed SLSDDL are low for Instrument and Mountain as compared to that of the KSVD. This is because KSVD performs better in terms of semantic detection for Instrument and Mountain video categories for TRECVID 2012 dataset.Table 3
The recognition rate of different video semantic analysis algorithms of TRECVID 2012.
Comparative methods LLC FDDL LSDL KSVD SLSDDL Accuracy (%) 65.89 64.49 76.97 76.60 84.83Figure 3
Recognition rate of TRECVID 2012 videos with different algorithms.


### 4.5. Experimental Results and Analysis: OV Video Dataset

The recognition rates of video semantic detection of the proposed SLSDDL with varying video features for the initial dictionaries are as indicated in Table4. It could be seen that the SLSDDL gives an optimum performance when the size of the dictionary is 122 x 500 and thus resulted in the highest accuracy of semantic analysis and hence is chosen.Table 4
Classification results on different dictionary atoms of OV dataset.
Number of the dictionary atoms 10 20 30 40 50 60 Accuracy (%) 63.7 74.6 77.1 83 84.97 82.8The recognition rates of LLC, FDDL, LSDL, KSVD, and SLSDDL are as shown in Table5. It could be seen that the proposed SLSDDL comparatively obtained the highest recognition rates than the other recognition approaches. As indicated by Figure 4, the average recognition rates of various video semantic detection methods associated with each class on the OV video dataset is also presented, which clearly suggests that the proposed method is best among all the comparative approaches on most categories. The recognition rate of the proposed method on the OV dataset, for instance, outperformed KSVD by 10.86% and 10.41% against LSDL, which goes to confirm the effectiveness of the proposed method. Hence, the proposed SLSDDL approach could effectively improve best the accuracy rates of OV video semantic feature detections.Table 5
The recognition rate of different video semantic analysis algorithms of OV dataset.
Comparative methods LLC FDDL LSDL KSVD SLSDDL Accuracy (%) 69.44 56.85 74.56 74.11 84.97Figure 4
Recognition rate of OV videos with different algorithms.


### 4.6. Experimental Results and Analysis: YouTube Video Dataset

The recognition rates of video semantic detection of the proposed SLSDDL with varying video features for the initial dictionaries are as indicated in Table6. It could be seen that the SLSDDL gives an optimum performance when the size of the dictionary is 122 x 550 and thus resulted in the highest accuracy of semantic analysis and hence is chosen.Table 6
Classification results on different dictionary atoms of YouTube.
The number of the dictionary atoms 10 20 30 40 50 60 Accuracy (%) 60.51 72.64 78.73 81.82 83.45 80.91The recognition rates of LLC, FDDL, LSDL, KSVD, and SLSDDL are as shown in Table7. It could be seen that the proposed SLSDDL comparatively obtained the highest recognition rates than the other recognition approaches. As indicated by Figure 5, the average recognition rates of various video semantic detection methods associated with each class on the YouTube video dataset are also presented, which clearly suggests that the proposed method is best among all the comparative approaches on most categories. The recognition rate of the proposed method on the YouTube dataset also outperformed KSVD by 8.9% and 9.36% against LSDL which confirms the effectiveness of the proposed method. Hence, the proposed SLSDDL approach could effectively improve best the accuracy rates of YouTube video semantic feature detections.Table 7
The recognition rate of different video semantic analysis algorithms of YouTube.
Comparative methods LLC FDDL LSDL KSVD SLSDDL Accuracy (%) 66.31 64 74.09 74.55 83.45Figure 5
Recognition rate of YouTube videos with different algorithms.


## 4.1. Video Shot Preprocessing

In the experiments, ordered samples clustering centered on artificial immune in [31] was adopted to extract the static image frames from each original video data utilizing the video key-frame extraction approach. Afterwards, features consisting of the 5-dimensional radial Tchebichef moment [32], 6-dimensional gray level cooccurrence matrix (GLCM) [33], 81-dimensional HSV color histogram [34], and 30-dimensional multiscale local binary pattern (LBP) [35] from the key-frame were extracted. The details of these features could be referred to in [2]. Figure 1 shows some key-frames of the three video datasets implemented.Figure 1
Some key frames from video shots for the respective datasets.
(a)
Some key frames from OV video set (b)
Part key frames from the TRECVID 2012 video set (c)
Part key frames from the YouTube video set


## 4.2. Database Selection and Video Analysis

Experiments are performed on natural images to demonstrate the efficient performance of our methods in this section. We analyze and compare the performance of our proposed algorithm with most typical algorithms such as the KSVD [11], FDDL, LLC [5], and LSDL [3] algorithms. Out of the many collections of datasets for video categorization and classification, three of them are being used in our experimental setup or evaluations. The public datasets being used are the TRECVID 2012 video dataset, OV video dataset, and YouTube video dataset.The TRECVID 2012 videos dataset has airplane, baby, building, car, dog, flower, instrumental_musician, mountain, scene_text, and speech as its video semantic models with each class containing 60 data sample; 50 of the samples were randomly as training samples, and the remaining as test samples.The YouTube video dataset iscomprised of basketball, biking, diving, golf_swing, horse_riding, soccer_juggling, swing, tennis, trampoline_jumping, volleyball, and walking as semantic videos with each class containing 70 data samples, out of which 60 were randomly selected as training samples, and the rest as test samples, and the semantic concepts ofthe OV dataset contain aircraft, sea, rocket, parachute, road, face, satellite, and star. Each class consists of 70 samples. For each class, 60 samples are randomly selected as training samples, and the remaining ones are testing samples. The proposed approach considered the L2 norm locality adaptor. The experimental results were realized by twentyfold cross-validation in which training samples are selected randomly and the remaining as the testing samples from the various video datasets.


## 4.3. Parameter Selection

Several parameters includingλ, the classification parameter, λ1, a positive weighing parameter for the locality-sensitive constraint, and λ2 for the discriminative constraint were utilized by the proposed SLSDDL and the classification error scheme, with varied values assigned depending on the dataset being used. More so, the classification parameter, λ, made a little or no effect on the output of the experimental results and hence was set to 0.01 in all experiments. The recognition rates of the proposed SLSDDL approach (for the optimization phase) with varying values of λ1 and λ2 on TRECVID dataset are as depicted by Figure 2. It could be seen from the figure that the optimum results were obtained for recognition when λ1 is 0.01 and λ2 is 0.007, respectively, with λ2 and λ1 values being fixed for each dataset by twentyfold cross validation. It is worth noting that different parameter values were realized for the experiment on the respective datasets because of the varying fundamental structure of the datasets. Based on the values stated in Table 1, an experiment was conducted to validate the performance of our proposed.Table 1
Parameter values implemented on the various data sets.
Dataset Parameter Values used λ 1 λ 2 TRECVID 2012 0.007 0.01 OV 0.006 0.03 YOUTUBE 0.5 0.01 Table1   indicates the various parameter selections with their respective datasets. Based on the aforementioned values, an experiment was conducted to validate the performance of our proposed algorithms and the findings are detailed below. Different datasets have different parameter settings because the structure of each dataset differs and hence the different parameter values.Figure 2
Recognition rate Vrs Variations of parameter values on TRECVID Dataset.


## 4.4. Experimental Results and Analysis: TRECVID 2012 Video Dataset

The recognition rates of video semantic detection of the proposed SLSDDL with varying video features for the initial dictionaries are as indicated in Table2. It could be seen that the SLSDDL gives an optimum performance when the size of the dictionary is 122 x 400 and thus resulted in the highest accuracy of semantic analysis and hence is chosen.Table 2
Classification results on different dictionary atoms of TRECVID 2012.
Number of the dictionary atoms 10 20 30 40 50 Accuracy Rate (%) 62 72.7 77.1 84.83 82.6The recognition rates of LLC, FDDL, LSDL, KSVD, and SLSDDL are as shown in Table3. It could be seen that the proposed SLSDDL comparatively obtained the highest recognition rates than the other recognition approaches. As indicated by Figure 3, the average recognition rates of various video semantic detection methods associated with each class on the TRECVID video dataset are also presented, which clearly suggests that the proposed method is best among all the comparative approaches on most categories. The recognition rate of the proposed method on the TRECVID dataset for instance outperformed KSVD by 8.23% and 7.86% against LSDL which confirms the effectiveness of the proposed method. Hence, the proposed SLSDDL approach could effectively improve best the accuracy rates of TRECVID video semantic feature detections. Nevertheless, the recognition rates for the proposed SLSDDL are low for Instrument and Mountain as compared to that of the KSVD. This is because KSVD performs better in terms of semantic detection for Instrument and Mountain video categories for TRECVID 2012 dataset.Table 3
The recognition rate of different video semantic analysis algorithms of TRECVID 2012.
Comparative methods LLC FDDL LSDL KSVD SLSDDL Accuracy (%) 65.89 64.49 76.97 76.60 84.83Figure 3
Recognition rate of TRECVID 2012 videos with different algorithms.


## 4.5. Experimental Results and Analysis: OV Video Dataset

The recognition rates of video semantic detection of the proposed SLSDDL with varying video features for the initial dictionaries are as indicated in Table4. It could be seen that the SLSDDL gives an optimum performance when the size of the dictionary is 122 x 500 and thus resulted in the highest accuracy of semantic analysis and hence is chosen.Table 4
Classification results on different dictionary atoms of OV dataset.
Number of the dictionary atoms 10 20 30 40 50 60 Accuracy (%) 63.7 74.6 77.1 83 84.97 82.8The recognition rates of LLC, FDDL, LSDL, KSVD, and SLSDDL are as shown in Table5. It could be seen that the proposed SLSDDL comparatively obtained the highest recognition rates than the other recognition approaches. As indicated by Figure 4, the average recognition rates of various video semantic detection methods associated with each class on the OV video dataset is also presented, which clearly suggests that the proposed method is best among all the comparative approaches on most categories. The recognition rate of the proposed method on the OV dataset, for instance, outperformed KSVD by 10.86% and 10.41% against LSDL, which goes to confirm the effectiveness of the proposed method. Hence, the proposed SLSDDL approach could effectively improve best the accuracy rates of OV video semantic feature detections.Table 5
The recognition rate of different video semantic analysis algorithms of OV dataset.
Comparative methods LLC FDDL LSDL KSVD SLSDDL Accuracy (%) 69.44 56.85 74.56 74.11 84.97Figure 4
Recognition rate of OV videos with different algorithms.


## 4.6. Experimental Results and Analysis: YouTube Video Dataset

The recognition rates of video semantic detection of the proposed SLSDDL with varying video features for the initial dictionaries are as indicated in Table6. It could be seen that the SLSDDL gives an optimum performance when the size of the dictionary is 122 x 550 and thus resulted in the highest accuracy of semantic analysis and hence is chosen.Table 6
Classification results on different dictionary atoms of YouTube.
The number of the dictionary atoms 10 20 30 40 50 60 Accuracy (%) 60.51 72.64 78.73 81.82 83.45 80.91The recognition rates of LLC, FDDL, LSDL, KSVD, and SLSDDL are as shown in Table7. It could be seen that the proposed SLSDDL comparatively obtained the highest recognition rates than the other recognition approaches. As indicated by Figure 5, the average recognition rates of various video semantic detection methods associated with each class on the YouTube video dataset are also presented, which clearly suggests that the proposed method is best among all the comparative approaches on most categories. The recognition rate of the proposed method on the YouTube dataset also outperformed KSVD by 8.9% and 9.36% against LSDL which confirms the effectiveness of the proposed method. Hence, the proposed SLSDDL approach could effectively improve best the accuracy rates of YouTube video semantic feature detections.Table 7
The recognition rate of different video semantic analysis algorithms of YouTube.
Comparative methods LLC FDDL LSDL KSVD SLSDDL Accuracy (%) 66.31 64 74.09 74.55 83.45Figure 5
Recognition rate of YouTube videos with different algorithms.


## 5. Conclusion and Recommendations

In this paper, a locality-sensitive discriminative dictionary learning based on sparsity is proposed. The proposed approach learns that video samples from the same category should be encoded as similar sparse coefficients in the process of video semantic detection based on sparse representation, so as to enhance the power of discrimination of sparse representation features. The paper also introduced into the structure of the locality-sensitive algorithm, a lost function centered on sparse coefficients to optimize the dictionary. The SLSDDL enhances the power of discrimination of sparse representation features based on the principles of Fishers for better dictionary optimization as a result of the constraints and also to improve video semantic classification.Based on the experimental results, it could be seen that the proposed SLSDDL algorithm for video semantic analysis is more effective and outperforms the other state-of-the-art approaches such as LLC, FDDL, LSDL, and KSVD. Despite superior results demonstrated by the proposed SLSDDL on the TRECVID, YouTube, and OV video datasets, there is still the need to improve the execution time and further improve the power of discrimination; hence we plan on using deep learning discussed in [36] for the extraction of the video features and also introducing kernel into the structure in our future work.



---

*Source: 9312563-2018-08-05.xml*