# Video Shot Boundary Recognition Based on Adaptive Locality Preserving Projections

Authors: Yongliang Xiao; Limin Xia; Shaoping Zhu; Dazu Huang; Jianquan Xie
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

A novel video shot boundary recognition method is proposed, which includes two stages of video feature extraction and shot boundary recognition. Firstly, we use adaptive locality preserving projections (ALPP) to extract video feature. Unlike locality preserving projections, we define the discriminating similarity with mode prior probabilities and adaptive neighborhood selection strategy which make ALPP more suitable to preserve the local structure and label information of the original data. Secondly, we use an optimized multiple kernel support vector machine to classify video frames into boundary and nonboundary frames, in which the weights of different types of kernels are optimized with an ant colony optimization method. Experimental results show the effectiveness of our method.


---

## Body

## 1. Introduction

Video shot boundary recognition is a fundamental process towards video summarization and analysis. There are many boundary recognition methods already presented [1, 2]. Common method to recognize shot boundary is comparing the difference of two adjacent frames with a threshold. In paper [3], the abrupt shot boundary is detected based on an adaptive threshold and gradual transition boundary is detected with a set of standard templates. Warhade et al. [4] detected shot boundary with cross-correlation coefficient, stationary wavelet transform, and combination of local. Thakar and Hadia [5] proposed a new gradual shot detection method in which the threshold can be adaptively determined based on the totaly information change of video frames. Huo et al. [6] used a statistical model according to the video frame differences to determine the adaptive threshold. In paper [7], the threshold is automatically determined according to the magnitude of color differences quantification. Warhade et al. [8] first extracted structure features from each video frame by using dual-tree complex wavelet transform and then decided the shot boundary based on the spatial domain similarity. In order to reduce the computation, Gao and Ma [9] used color histogram and mutual information to measure the difference between frames, and then the corner distribution of frames is utilized to exclude most of the false boundaries.The main disadvantage of these methods is susceptible to the effect of thresholds, which can make a mistake for some complicated long gradual shots. To resolve this problem, people see the video shot recognition as a categorization task. In paper [10], a fuzzy logic method is used to detect shot boundary. This method contains two processing modes, where one is dedicated to detection of abrupt shot and the other for detection of gradual shot. In paper [11], the video feature including HSV (hue, saturation, value), edge orientation, and texture feature is obtained, and then the Kohonen self-organized network is used to recognize shot boundary. Huang et al. [12] classified video frames with a radial basis function neural network. Mohanta et al. [13] used a multilayer perception network to classify video frames based on local features matrix. To improve the recognition performance, Li et al. [14] first removed some frames from the original video which were clearly not shot boundaries, then used a novel SIFT key point matching algorithm to detect shot boundary. Zhao et al. [15] used context feature vector and Tabu-SVM to recognize shot boundary. In paper [16], the proposed approach first detected general shot boundary with Fisher criterion and then classified the cut and gradual shot with SVM. In order to improve the effect of SVM, Zhao et al. [17] optimized the parameters of SVM with particle swarm method. In addition, Lankinen and Kamarainen [18] detected shot boundary using a visual bag-of-words approach. Donate and Liu [19] extracted salient features from a video sequence and tracked them over time to estimate shot boundaries. Li and Chen [20] recognized shot boundary with macroblock type information which can save a lot of computation cost.In this paper, we present a novel method to improve the shot boundary recognition accuracy. Firstly, based on the analysis of LPP, we present an adaptive LPP to extract more useful and discriminating features. Secondly, we recognize shot boundary with an optimized multiple kernel support vector machine.The rest of this paper is organized as follows. Section2 abstracts the theoretical fundamentals about LPP. In Section 3, we extract the video feature with improved LPP. Section 4 uses an optimized multiple kernel SVM to recognize shot boundary. Some experiments are used to evaluate the presented method in Section 5 and all the paper is concluded in Section 6.


## 2. Theoretical Fundamentals

### 2.1. Locality Preserving Projection

Locality preserving projection (LPP) is a dimensionality reduction method which can be explained by the graph theory [21]. Assume there ism-dimensional data point setX=[x1,x2,…,xn]; we try to find a project matrixAto project these data point into a low-dimensional subspace, and the projection can be expressed asyi=ATxi.The objective function of LPP is as follows:(1)min∑ij∥yi-yj∥2Sij,
where the weight matrixScan be defined as follows:
(2)Sij={1ifxiisamongKnearestneighborsofxjorxjisamongKnearestneighborsofxi0else.
Then, the objective function of LPP can be converted into the following minimization problem:
(3)minAtr{ATXLXTA}s.t.ATXDXTA=1,
whereDij=∑jWijis a diagonal matrix andL=D-Sis a Laplacian matrix.Lastly, the project matrixAcan be obtained by solving a generalized eigenvalue problem as follows:
(4)XLXTA=λXDXTA.Let the column vectorsa1,a2,…,adbe the solutions of (4), ordered according to their eigenvalues,λ1,λ2,…,λd; we can define the following transformation form:
(5)xi⟶yi=ATxi,A=[a1,a2,…,ad].


### 2.2. Weight Definition

In the LPP, the weight between two points is defined to be a simple either 1 or 0 or heat kernel, which cannot reflect the class information. GivenX=[x1,x2,…,xn], letCiandN(xi)be the label andkthe nearest neighbors of the pointxi, Li et al. [22] presented an orthogonal discriminating projection (ODP), in which the weightSijbetween two points is defined as follows:
(6)Sij={exp(-d2(xi,xj)β)ifxi∈N(xj),xj∈N(xi),Ci=Cjexp(-d2(xi,xj)β)(1-exp(-d2(xi,xj)β))ifxi∈N(xj),xj∈N(xi),Ci=Cj0otherwise,
whered(xi,xj)denote the geodesic distance between pointsxiandxj, andβis a parameter which is used as a regular.Figure1 shows that the typical plot ofSijis a function ofd2(xi,xj)/β, whereS1=exp(-d2(xi,xj)/β),  S2=exp(-d2(xi,xj)/β)(1-exp(-d2(xi,xj)/β)),   S3=0.Figure 1
Type plot ofSijas a function ofd2(xi,xj)/β.From Figure1 we find thatSijis not a monotonically decreasing function ofd2(xi,xj)/β, which is due to the fact thatS2is a nonmonotonic function. When0<d2(xi,xj)/β<0.71,Sijis monotonically increasing. In the actual applications,Sijshould decrease with the increase ofd2(xi,xj)/β. Zhang et al. [23] proposed a modified ODP (MODP) with correlation coefficient∥(xi-x-i)(xj-x-j)∥/∥(xi-x-i)∥·∥(xj-x-j)∥betweenxiandxj.Obviously, the above definitions aboutSijconsider only the space structure and not the manifold structure. Meanwhile, the presentedknearest neighbors do not reflect the real information of manifold structure.


## 2.1. Locality Preserving Projection

Locality preserving projection (LPP) is a dimensionality reduction method which can be explained by the graph theory [21]. Assume there ism-dimensional data point setX=[x1,x2,…,xn]; we try to find a project matrixAto project these data point into a low-dimensional subspace, and the projection can be expressed asyi=ATxi.The objective function of LPP is as follows:(1)min∑ij∥yi-yj∥2Sij,
where the weight matrixScan be defined as follows:
(2)Sij={1ifxiisamongKnearestneighborsofxjorxjisamongKnearestneighborsofxi0else.
Then, the objective function of LPP can be converted into the following minimization problem:
(3)minAtr{ATXLXTA}s.t.ATXDXTA=1,
whereDij=∑jWijis a diagonal matrix andL=D-Sis a Laplacian matrix.Lastly, the project matrixAcan be obtained by solving a generalized eigenvalue problem as follows:
(4)XLXTA=λXDXTA.Let the column vectorsa1,a2,…,adbe the solutions of (4), ordered according to their eigenvalues,λ1,λ2,…,λd; we can define the following transformation form:
(5)xi⟶yi=ATxi,A=[a1,a2,…,ad].


## 2.2. Weight Definition

In the LPP, the weight between two points is defined to be a simple either 1 or 0 or heat kernel, which cannot reflect the class information. GivenX=[x1,x2,…,xn], letCiandN(xi)be the label andkthe nearest neighbors of the pointxi, Li et al. [22] presented an orthogonal discriminating projection (ODP), in which the weightSijbetween two points is defined as follows:
(6)Sij={exp(-d2(xi,xj)β)ifxi∈N(xj),xj∈N(xi),Ci=Cjexp(-d2(xi,xj)β)(1-exp(-d2(xi,xj)β))ifxi∈N(xj),xj∈N(xi),Ci=Cj0otherwise,
whered(xi,xj)denote the geodesic distance between pointsxiandxj, andβis a parameter which is used as a regular.Figure1 shows that the typical plot ofSijis a function ofd2(xi,xj)/β, whereS1=exp(-d2(xi,xj)/β),  S2=exp(-d2(xi,xj)/β)(1-exp(-d2(xi,xj)/β)),   S3=0.Figure 1
Type plot ofSijas a function ofd2(xi,xj)/β.From Figure1 we find thatSijis not a monotonically decreasing function ofd2(xi,xj)/β, which is due to the fact thatS2is a nonmonotonic function. When0<d2(xi,xj)/β<0.71,Sijis monotonically increasing. In the actual applications,Sijshould decrease with the increase ofd2(xi,xj)/β. Zhang et al. [23] proposed a modified ODP (MODP) with correlation coefficient∥(xi-x-i)(xj-x-j)∥/∥(xi-x-i)∥·∥(xj-x-j)∥betweenxiandxj.Obviously, the above definitions aboutSijconsider only the space structure and not the manifold structure. Meanwhile, the presentedknearest neighbors do not reflect the real information of manifold structure.


## 3. Video Feature Reduction

In this section, we extract more discriminating video features from the original color, shape, and texture feature. Firstly, we propose an improved LPP. We adaptively select theknearest neighbors of each point and introduce the model information into the new weight similarity which can make the weight be a monotonically decreasing function of distance. The major merit of ALPP is preserving the local structure and label information of original data. Then we use ALPP to extract more discriminating video features for shot boundary recognition.


### 3.1. Mode Detection

In order to preserve the mode information of data points, we use median-shift method relied on computing the median of local neighborhoods instead of the mean to detect mode. Considering that the median of a set is a point in the set, the method is more robust than mean-shift method. Most importantly, the median-shift method is not a nonparametric method that does not require a prior knowledge of the number of clusters nor does it place any limitations on the shape of the clusters. The process of mode detection is as follows [24].Suppose we are given a setS={s1,…,sn},  si∈Rd,  d>1; define the Tukey depth of a point to be
(7)DEPTH(si)=min[vTsi:v∈Rd,∥v∥=1],
where the Tukey depth of a point is the minimum of its depth along any projection vectorv.Firstly, the median ofSis an element with maximal depth
(8)MEDIAN(S)=maxsi∈S(∑vk∈VDEPTH(siTvk)).Then we seek the mode with the median-shift algorithms. For each point we wish to ascend in the direction of the positive gradient of the underlying probability density function. We define the median-shift for pointcin setPas
(9)c′=MEDIAN(p∈P∣∥p-c∥≤R),
whereris a bandwidth parameter. Sincec′uses necessarily a point in the dataset, there is no need for multiple iterations in this step. After one iteration all points are linked and we can only go through the list of discovered medians to find a mode. The results of this step are a set of modes representing clusters.Next, we proceed by iteratively working on the reduced set of modes, replacing the median calculation by weighted median calculation until convergence, where weights are the number of points mapped to the given mode. The weights are taken into account during the calculation of the depth of each point in the next iteration by modifying the definitions as follows:(10)RANK(si)=∑sj<siWeight(sj)
and definingW=∑sjWeight(sj)as the total weights in the neighborhood ofsi, then
(11)DEPTH(si)=min(RANK(si),W-RANK(si)).Finally, in case of data clustering, and not only mode detection, we map each data point to its closest mode. LetMibe the model of the pointxi, and letMbe the set ofMimode; we can obtain
(12)M={M1,M2,…,MM},
whereMm={xj∣xj∈M∧model(xj)=m}.


### 3.2. Adaptive Neighborhood Selection

Considering the unchangeablekneighborhood not reflecting the mode information of manifold structure, we apply an adaptive strategy to select the neighborhood of each point.Firstly, we define the manifold adjusted length of line segment(13)L(xi,xj)={ρd(xi,xj)-1xiandxjareneighboringpointsinfiniteelse,
whered(xi,xj)is the Euclidean distance betweenxiandxjandρis a flexing factor. Obviously, this formulation can be utilized to describe the global consistency. In addition, the length of line segment between two points can be elongated or shortened by adjusting the flexing factorρ[25].Then, let data points be the nodes of graphG=(V;E)and letp∈Vlbe a path of lengthl=|p|-1connecting the nodesp1andp|p|in which(pk,pk+1)∈E,  1≤k≤|p|. LetPijdenote the set of all paths connecting nodesxiandxj; the manifold distance metric between two points is defined as follows:
(14)D(xi,xj)=minp∈Pi∑k=1|p|-1L(pk,pk+1),
whereL(a,b)denotes the manifold adjusted length of line segment.Next, the average manifold distance of pointxiis defined as follows:
(15)MS(xi)=1Nm∑Mi=MjD(xi,xj),
whereNmis the total number which meets the conditionsMi=Mj.Lastly, the adaptive neighborhood of pointxiis constructed as
(16)N′(xi)={x∣D(xi,xj)<MS(xi)∧Mi=Mj}
which shows that the neighborhood of pointxiis adaptively built with the points where the distance is shorter than the average distance.The major merit of the adaptive neighborhood selection method can be summarized as follows.(1)
The manifold distance metric can measure the geodesic distance along the manifold, which can elongate the distance among data points in different regions of high density and simultaneously shorten that in the same region of high density.(2)
The neighborhood of each point is different from others, which is decided by the local density of the origin space. When the local density ofxiis lower, the neighborhood is higher and vice versa.


### 3.3. Improve Weight Definition

In order to resolve the problem which is described in Section2.2, we improve the weight definition between two pointsxiandxjas follows:
(17)Sij={exp(-d2(xi,xj)β1)ifxi∈N′(xj),xi∈N′(xj),Ci=Cjexp(-d2(xi,xj)β1)exp(-d2(xi,xj)β2)ifxi∈N′(xj),xi∈N′(xj),Ci=Cj0otherwise,
whered(xi,xj)denotes the distance between pointsxiandxj,   β1andβ2are the regular parameters, andCiis the label of the pointxifor definition ofN′(xi)please refer to (16).Figure2 shows that the typical plot ofSijis a function ofd2(xi,xj)/β,   β=β1=β2, whereS1=exp(-d2(xi,xj)/β1),  S2=exp(-d2(xi,xj)/β1)exp(-d2(xi,xj)/β2), andS3=0.Figure 2
Type plot ofSijas a function ofd2(xi,xj)/β.Similar to paper [26], letexp(-d2(xi,xj)/β1)be the local weight, and letexp(-d2(xi,xj)/β2)be the intermode discriminating weight. The new weight definition can be viewed as the local weight and discriminating weight. It means that the discriminating similarity reflects both the local neighborhood structure of model and label information of the data set.The properties and the corresponding advantages of the improved weight definition can be summarized as follows.(1)
The improved weight definition make use of the label information and model information to preserve the manifold information, which is very important for classification.(2)
Since the value ofexp(-d2(xi,xj)/β2)ranges from 0 to 1, no matter how far the two points are, the inter-mode similarity can be limited in certain ranges.(3)
With the decrease of the geodesic distance,exp(-d2(xi,xj)/β2)is a decrease, which means that two near points from different modes have a smaller similarity.(4)
Note thatS1andS2always decrease whenxiandxjare far apart and they increase whenxiandxjare close. Thus,Sijis a monotonically decreasing function ofd2(xi,xj)/β.(5)
The use of mode prior probabilities makes the newly designed discriminating similaritySijmore suitable for perverting the local structure information of original data.


### 3.4. Video Feature Reduction

In order to enhance the discriminating information for shot boundary recognition, we hope to combine the label information and model information to improve the discriminating ability and preserve the local neighborhood structure of the original data.Due to introducing the similarity matrixS, we define the local scatter matrix as follows [23]:
(18)JL(A)=∑i=1n∑j=1nSij(yi-yj)(yi-yj)T=∑i=1n∑j=1nSij(ATxi-ATxj)(ATxi-ATxj)T=ATSLA,
whereSL=∑i=1n∑j=1nSij(xi-xj)(xi-xj)T=XLXT,  L=M-S,  Mii=∑jSij.Then we define the nonlocal scatter matrix as follows:(19)JN(A)=∑i=1n∑j=1n(1-Sij)(yi-yj)(yi-yj)T=∑i=1n∑j=1n(1-Sij)(ATxi-ATxj)(ATxi-ATxj)T=AT(ST-SN)A=ATSNA,
whereST=∑i=1n∑j=1n(xi-xj)(xi-xj)T,  SN=ST-SL.Lastly, the objective function of the improved LPP can be expressed as follows:(20)argmaxAJ(A)=argmaxAT((1-α)ST-αSL)As.t.ATA=I,
whereαis an adjustable factor.So we can find thatAconsists of the eigenvectors associated withdtop eigenvalues of the following eigen-equation:
(21)((1-α)ST-αSL)a=λa.The algorithmic procedure of video feature extraction is stated below.(1)
Extract original video feature including the color, shape and texture feature.(2)
Perform PCA projection. In order to make the matrixXXTbecome nonsingular, we project the dataset into a PCA subspace with a transformation matrix.(3)
Define the similarity matrix. For each pointxi, compute the similarityWij=exp(-d2(xi,xj)/β1), ifxjis the adaptive neighbors ofxiandci=cj, and compute the similarityWij=exp(-d2(xi,xj)/β1)exp(-d2(xi,xj)/β2), ifxjis the adaptive neighbors ofxiandci≠cj.(4)
Compute the diagonal matrixMand Laplacian matrixLand then compute the topdeigenvalues and its corresponding eigenvectors based on (20).(5)
Perform the ALPP transformation. LetAbe an optimal projection matrix; we can project the new data into low dimensionality with
(22)Y=ATX.


## 3.1. Mode Detection

In order to preserve the mode information of data points, we use median-shift method relied on computing the median of local neighborhoods instead of the mean to detect mode. Considering that the median of a set is a point in the set, the method is more robust than mean-shift method. Most importantly, the median-shift method is not a nonparametric method that does not require a prior knowledge of the number of clusters nor does it place any limitations on the shape of the clusters. The process of mode detection is as follows [24].Suppose we are given a setS={s1,…,sn},  si∈Rd,  d>1; define the Tukey depth of a point to be
(7)DEPTH(si)=min[vTsi:v∈Rd,∥v∥=1],
where the Tukey depth of a point is the minimum of its depth along any projection vectorv.Firstly, the median ofSis an element with maximal depth
(8)MEDIAN(S)=maxsi∈S(∑vk∈VDEPTH(siTvk)).Then we seek the mode with the median-shift algorithms. For each point we wish to ascend in the direction of the positive gradient of the underlying probability density function. We define the median-shift for pointcin setPas
(9)c′=MEDIAN(p∈P∣∥p-c∥≤R),
whereris a bandwidth parameter. Sincec′uses necessarily a point in the dataset, there is no need for multiple iterations in this step. After one iteration all points are linked and we can only go through the list of discovered medians to find a mode. The results of this step are a set of modes representing clusters.Next, we proceed by iteratively working on the reduced set of modes, replacing the median calculation by weighted median calculation until convergence, where weights are the number of points mapped to the given mode. The weights are taken into account during the calculation of the depth of each point in the next iteration by modifying the definitions as follows:(10)RANK(si)=∑sj<siWeight(sj)
and definingW=∑sjWeight(sj)as the total weights in the neighborhood ofsi, then
(11)DEPTH(si)=min(RANK(si),W-RANK(si)).Finally, in case of data clustering, and not only mode detection, we map each data point to its closest mode. LetMibe the model of the pointxi, and letMbe the set ofMimode; we can obtain
(12)M={M1,M2,…,MM},
whereMm={xj∣xj∈M∧model(xj)=m}.


## 3.2. Adaptive Neighborhood Selection

Considering the unchangeablekneighborhood not reflecting the mode information of manifold structure, we apply an adaptive strategy to select the neighborhood of each point.Firstly, we define the manifold adjusted length of line segment(13)L(xi,xj)={ρd(xi,xj)-1xiandxjareneighboringpointsinfiniteelse,
whered(xi,xj)is the Euclidean distance betweenxiandxjandρis a flexing factor. Obviously, this formulation can be utilized to describe the global consistency. In addition, the length of line segment between two points can be elongated or shortened by adjusting the flexing factorρ[25].Then, let data points be the nodes of graphG=(V;E)and letp∈Vlbe a path of lengthl=|p|-1connecting the nodesp1andp|p|in which(pk,pk+1)∈E,  1≤k≤|p|. LetPijdenote the set of all paths connecting nodesxiandxj; the manifold distance metric between two points is defined as follows:
(14)D(xi,xj)=minp∈Pi∑k=1|p|-1L(pk,pk+1),
whereL(a,b)denotes the manifold adjusted length of line segment.Next, the average manifold distance of pointxiis defined as follows:
(15)MS(xi)=1Nm∑Mi=MjD(xi,xj),
whereNmis the total number which meets the conditionsMi=Mj.Lastly, the adaptive neighborhood of pointxiis constructed as
(16)N′(xi)={x∣D(xi,xj)<MS(xi)∧Mi=Mj}
which shows that the neighborhood of pointxiis adaptively built with the points where the distance is shorter than the average distance.The major merit of the adaptive neighborhood selection method can be summarized as follows.(1)
The manifold distance metric can measure the geodesic distance along the manifold, which can elongate the distance among data points in different regions of high density and simultaneously shorten that in the same region of high density.(2)
The neighborhood of each point is different from others, which is decided by the local density of the origin space. When the local density ofxiis lower, the neighborhood is higher and vice versa.


## 3.3. Improve Weight Definition

In order to resolve the problem which is described in Section2.2, we improve the weight definition between two pointsxiandxjas follows:
(17)Sij={exp(-d2(xi,xj)β1)ifxi∈N′(xj),xi∈N′(xj),Ci=Cjexp(-d2(xi,xj)β1)exp(-d2(xi,xj)β2)ifxi∈N′(xj),xi∈N′(xj),Ci=Cj0otherwise,
whered(xi,xj)denotes the distance between pointsxiandxj,   β1andβ2are the regular parameters, andCiis the label of the pointxifor definition ofN′(xi)please refer to (16).Figure2 shows that the typical plot ofSijis a function ofd2(xi,xj)/β,   β=β1=β2, whereS1=exp(-d2(xi,xj)/β1),  S2=exp(-d2(xi,xj)/β1)exp(-d2(xi,xj)/β2), andS3=0.Figure 2
Type plot ofSijas a function ofd2(xi,xj)/β.Similar to paper [26], letexp(-d2(xi,xj)/β1)be the local weight, and letexp(-d2(xi,xj)/β2)be the intermode discriminating weight. The new weight definition can be viewed as the local weight and discriminating weight. It means that the discriminating similarity reflects both the local neighborhood structure of model and label information of the data set.The properties and the corresponding advantages of the improved weight definition can be summarized as follows.(1)
The improved weight definition make use of the label information and model information to preserve the manifold information, which is very important for classification.(2)
Since the value ofexp(-d2(xi,xj)/β2)ranges from 0 to 1, no matter how far the two points are, the inter-mode similarity can be limited in certain ranges.(3)
With the decrease of the geodesic distance,exp(-d2(xi,xj)/β2)is a decrease, which means that two near points from different modes have a smaller similarity.(4)
Note thatS1andS2always decrease whenxiandxjare far apart and they increase whenxiandxjare close. Thus,Sijis a monotonically decreasing function ofd2(xi,xj)/β.(5)
The use of mode prior probabilities makes the newly designed discriminating similaritySijmore suitable for perverting the local structure information of original data.


## 3.4. Video Feature Reduction

In order to enhance the discriminating information for shot boundary recognition, we hope to combine the label information and model information to improve the discriminating ability and preserve the local neighborhood structure of the original data.Due to introducing the similarity matrixS, we define the local scatter matrix as follows [23]:
(18)JL(A)=∑i=1n∑j=1nSij(yi-yj)(yi-yj)T=∑i=1n∑j=1nSij(ATxi-ATxj)(ATxi-ATxj)T=ATSLA,
whereSL=∑i=1n∑j=1nSij(xi-xj)(xi-xj)T=XLXT,  L=M-S,  Mii=∑jSij.Then we define the nonlocal scatter matrix as follows:(19)JN(A)=∑i=1n∑j=1n(1-Sij)(yi-yj)(yi-yj)T=∑i=1n∑j=1n(1-Sij)(ATxi-ATxj)(ATxi-ATxj)T=AT(ST-SN)A=ATSNA,
whereST=∑i=1n∑j=1n(xi-xj)(xi-xj)T,  SN=ST-SL.Lastly, the objective function of the improved LPP can be expressed as follows:(20)argmaxAJ(A)=argmaxAT((1-α)ST-αSL)As.t.ATA=I,
whereαis an adjustable factor.So we can find thatAconsists of the eigenvectors associated withdtop eigenvalues of the following eigen-equation:
(21)((1-α)ST-αSL)a=λa.The algorithmic procedure of video feature extraction is stated below.(1)
Extract original video feature including the color, shape and texture feature.(2)
Perform PCA projection. In order to make the matrixXXTbecome nonsingular, we project the dataset into a PCA subspace with a transformation matrix.(3)
Define the similarity matrix. For each pointxi, compute the similarityWij=exp(-d2(xi,xj)/β1), ifxjis the adaptive neighbors ofxiandci=cj, and compute the similarityWij=exp(-d2(xi,xj)/β1)exp(-d2(xi,xj)/β2), ifxjis the adaptive neighbors ofxiandci≠cj.(4)
Compute the diagonal matrixMand Laplacian matrixLand then compute the topdeigenvalues and its corresponding eigenvectors based on (20).(5)
Perform the ALPP transformation. LetAbe an optimal projection matrix; we can project the new data into low dimensionality with
(22)Y=ATX.


## 4. Shot Boundary Recognition

The process of shot boundary detection includes two steps. Firstly, we extract the video features using ALPP method. Secondly, we detect shot boundary using an optimized MKSVM.


### 4.1. Multiple Kernel SVM

Support vector machines are a family of pattern classification algorithms which is based on the idea of structural risk minimization rather than empirical risk minimization [27]. However, it is often unclear what the most suitable kernel for the task at hand is. Recently, the multiple kernel learning theory has been used for training different kernels by jointly optimizing both the coefficients of the classifiers and the weights of the kernels which have a more excellent effectiveness for object recognition than SVM [28]. In this paper, we combine several possible kernels to improve the precision of shot boundary recognition.Letd=[d1,d2,…dM]Tbe a vector of weights for the mixture of kernels. A multiple kernel is the combination of theMbasis kernelsKm(23)K(xi,xj)=∑i=1MdmKm(xi,xj)s.t.dm≥0s.t.∑i=1Mdm=1.Assume there are a data setD={xi,zi}i=1mof labeled examples, wherexi∈Xis the input vector andzi∈{-1,1}.According to paper [29], the primal form of multiple kernel support vector machine (MKSVM) is thus formulated as the following optimization problem:
(24)mind,b,ξJ(d)=12∑m=1M1dm∥fm∥2+C∑i=1lξis.t.yi∑i=1nfm(xi)+yib≥1-ξis.t.ξi≥0,∀is.t.∑i=1mdm=1,dm≥0,∀m.Similar to the SVM, with the constraint ondm, the above minimization problem can thus be transformed into the following dual problem:
(25)maxα∑i=1nαi-12∑i,j=1nαiαjyiyj∑i=1Mdmk(xi,xj)s.t.∑i=1nyiαi=0,∀i=1,…,ns.t.0≤αi≤C,∑i=1Mdm=1,dm≥0.For the test inputx, the decision function of MKSVM can be computed as
(26)FMKL(x)=sign(∑i=1n∑m=1MdmKm(xi,x)ai+b).


### 4.2. Ant Colony Optimization Method

Ant colony optimization method (ACO) is an optimizing method inspired by the foraging behavior of ant colonies [30]. When ants walk between their nest and a food source, they mark the paths with special kind of chemical termed pheromone, and the shorter paths can attract more and more pheromone [31]. In the method, an ant determines its transfer direction according to the amount of pheromone in each path. Firstly, every ant constructs an edge from a start vertex to an end vertex. Then when all ants reach the end vertex, the edges are marked with a pheromone quantity. Thus the colony can converge to the shortest path [32]. In this paper, we apply the ant colony optimization method to solve the weights optimized problem in MKSVM.LetPijk(t)be the proximity which an antktransfer from elementitojat iterationt.Pijk(t)can be defined as
(27)Pijk(t)={τijα(i-1)ηijβ∑z∈Vk(x)τijα(i-1)ηijβifz∈Vk(x)0else,
whereVk(x)is the element which has not been unvisited.τijis the pheromone quantity of path(i,j),ηijis a heuristic measure of moving elementito elementj,α, andβare two parameters that control the relative importance of the information heuristics and exception heuristics factor, respectively.The amount ofpallmants pheromone trail on a path deposited step by step. After timem, the pheromone quantityτij(t)associated with an edge joining elementiandjis updated according to the following formula:
(28)τij(t+m)=(1-ρ)τij(t-1)+∑k=1nΔτijk(t),
whereρis a pheromone evaporation loss coefficient andΔτijk(t)is the pheromone quantity deposited at iterationiby antkon an edge joining elementiandj. TheΔτijk(t)is usually defined as
(29)Δτijk(i)={QLkifwij∈Tk(I)0else,
whereQis a constant andLkis the cost function ofkth ant.For the process of ant colony optimization method please refer to paper [33].


### 4.3. Shot Boundary Recognition

The process of shot boundary recognition includes the following stages. Firstly, we extract the original feature. Then we reduce the video feature with improved LPP. Lastly, we classify the frame into boundary frame with the optimized MKSVM classifier based on ACO method.The algorithm of video boundary recognition is described as follows.(1)
Extract original video feature which includes colors, shape, and texture feature.(2)
Reduce video feature with improved LPP.(3)
Define input vector[(yi-k-yi),…,(yi+k-yi)], whereyiis the video feature vector andiisith frame of video.(4)
Label the boundary frames(+1)and nonboundary frame(-1)and build training sample set.(5)
Initialize the parameters of ACO. Let timet=0, interactive timesIt=0. Set the maximum iterative timesIt(max)and let initial pheromoneτxy=candΔτxy(0)=0.(6)
UpdateItbyIt=It+1and choose the ant elementjas its transform direction according to function (27).(7)
Update the taboo table pointer. Move the ant to the selected new element and add the element into ant taboo table.(8)
If all elements of the set have been fully traversed, go to step 7 or else go to the next step.(9)
Recalculate the pheromone of each path, ifIt<It(max), go to step 6, or else save the weightsd=[d1,d2,…dM].(10)
Classify the video frame into boundary frame based on the following rule:(30)FMKL(x)=sign(∑i=1n∑m=1MdmKm(xi,x)ai+b).


## 4.1. Multiple Kernel SVM

Support vector machines are a family of pattern classification algorithms which is based on the idea of structural risk minimization rather than empirical risk minimization [27]. However, it is often unclear what the most suitable kernel for the task at hand is. Recently, the multiple kernel learning theory has been used for training different kernels by jointly optimizing both the coefficients of the classifiers and the weights of the kernels which have a more excellent effectiveness for object recognition than SVM [28]. In this paper, we combine several possible kernels to improve the precision of shot boundary recognition.Letd=[d1,d2,…dM]Tbe a vector of weights for the mixture of kernels. A multiple kernel is the combination of theMbasis kernelsKm(23)K(xi,xj)=∑i=1MdmKm(xi,xj)s.t.dm≥0s.t.∑i=1Mdm=1.Assume there are a data setD={xi,zi}i=1mof labeled examples, wherexi∈Xis the input vector andzi∈{-1,1}.According to paper [29], the primal form of multiple kernel support vector machine (MKSVM) is thus formulated as the following optimization problem:
(24)mind,b,ξJ(d)=12∑m=1M1dm∥fm∥2+C∑i=1lξis.t.yi∑i=1nfm(xi)+yib≥1-ξis.t.ξi≥0,∀is.t.∑i=1mdm=1,dm≥0,∀m.Similar to the SVM, with the constraint ondm, the above minimization problem can thus be transformed into the following dual problem:
(25)maxα∑i=1nαi-12∑i,j=1nαiαjyiyj∑i=1Mdmk(xi,xj)s.t.∑i=1nyiαi=0,∀i=1,…,ns.t.0≤αi≤C,∑i=1Mdm=1,dm≥0.For the test inputx, the decision function of MKSVM can be computed as
(26)FMKL(x)=sign(∑i=1n∑m=1MdmKm(xi,x)ai+b).


## 4.2. Ant Colony Optimization Method

Ant colony optimization method (ACO) is an optimizing method inspired by the foraging behavior of ant colonies [30]. When ants walk between their nest and a food source, they mark the paths with special kind of chemical termed pheromone, and the shorter paths can attract more and more pheromone [31]. In the method, an ant determines its transfer direction according to the amount of pheromone in each path. Firstly, every ant constructs an edge from a start vertex to an end vertex. Then when all ants reach the end vertex, the edges are marked with a pheromone quantity. Thus the colony can converge to the shortest path [32]. In this paper, we apply the ant colony optimization method to solve the weights optimized problem in MKSVM.LetPijk(t)be the proximity which an antktransfer from elementitojat iterationt.Pijk(t)can be defined as
(27)Pijk(t)={τijα(i-1)ηijβ∑z∈Vk(x)τijα(i-1)ηijβifz∈Vk(x)0else,
whereVk(x)is the element which has not been unvisited.τijis the pheromone quantity of path(i,j),ηijis a heuristic measure of moving elementito elementj,α, andβare two parameters that control the relative importance of the information heuristics and exception heuristics factor, respectively.The amount ofpallmants pheromone trail on a path deposited step by step. After timem, the pheromone quantityτij(t)associated with an edge joining elementiandjis updated according to the following formula:
(28)τij(t+m)=(1-ρ)τij(t-1)+∑k=1nΔτijk(t),
whereρis a pheromone evaporation loss coefficient andΔτijk(t)is the pheromone quantity deposited at iterationiby antkon an edge joining elementiandj. TheΔτijk(t)is usually defined as
(29)Δτijk(i)={QLkifwij∈Tk(I)0else,
whereQis a constant andLkis the cost function ofkth ant.For the process of ant colony optimization method please refer to paper [33].


## 4.3. Shot Boundary Recognition

The process of shot boundary recognition includes the following stages. Firstly, we extract the original feature. Then we reduce the video feature with improved LPP. Lastly, we classify the frame into boundary frame with the optimized MKSVM classifier based on ACO method.The algorithm of video boundary recognition is described as follows.(1)
Extract original video feature which includes colors, shape, and texture feature.(2)
Reduce video feature with improved LPP.(3)
Define input vector[(yi-k-yi),…,(yi+k-yi)], whereyiis the video feature vector andiisith frame of video.(4)
Label the boundary frames(+1)and nonboundary frame(-1)and build training sample set.(5)
Initialize the parameters of ACO. Let timet=0, interactive timesIt=0. Set the maximum iterative timesIt(max)and let initial pheromoneτxy=candΔτxy(0)=0.(6)
UpdateItbyIt=It+1and choose the ant elementjas its transform direction according to function (27).(7)
Update the taboo table pointer. Move the ant to the selected new element and add the element into ant taboo table.(8)
If all elements of the set have been fully traversed, go to step 7 or else go to the next step.(9)
Recalculate the pheromone of each path, ifIt<It(max), go to step 6, or else save the weightsd=[d1,d2,…dM].(10)
Classify the video frame into boundary frame based on the following rule:(30)FMKL(x)=sign(∑i=1n∑m=1MdmKm(xi,x)ai+b).


## 5. Experiments and Analysis

In this section we present some experiments to validate the proposed approach. Firstly, we investigate the performance of the proposed ALPP method for video feature exaction experiment. Then we recognize shot boundary with the proposed method. The video database includes movie, news, sports, documentary, and MTV. The reason of selecting this type video is that news videos have many long abrupt shots, MTV has fast changes of scenes, sport have fast camera movements and zooming in, movie includes many gradual shots. Some shot samples are shown in Figure3. For evaluation, we use the common figures of merit of the algorithm standard precision and recall [34]
(31)Precision=#(Boundariescorrectlydetected)#(Totalboundariesdetected),Recall=#(Boundariescorrectlydetected)#(Totalgroundtruthboundaries).Some shot samples.
(a)
Abrupt shot
(b)
Dissolve shot
(c)
Fade out shot


### 5.1. Video Feature Exaction Experiment

In order to testify the effectiveness of the adaptive LPP (ALPP), we extract video feature with ODP, MODP, and ALPP method. For convenience of comparison, we use the same method in paper [35] to detect shot boundary. In the experiment, original video feature is built on color feature, shape feature, and texture feature. Then ODP, MODP, and ALPP method, are used to extract video feature withα=0.5andγ=0.6. In the ODP and MODP methods we adoptknearest neighbor criterion to define the adjacency matrix, in which thekset to 10. The results of performance comparison by using ODP, MODP, and ALPP are shown in Table 1.Table 1
Comparison results between ODP, MODP, and ALPP.
Methods
OPP
MODP
ALPP
Precision
83.7
86.1
89.6
Recall
85.5
87.8
90.4From Table1, we can find that ALPP obtains comparable recognition performance to LPP and ODP with the same shot boundary detect method. In ALPP method, the improved weight definition combines the label information and model information with adaptive nearest neighbor select strategy, which is very important to reflect the data information truthfully. The experiment shows that ALPP has more useful and discriminating ability to extract video feature than others.


### 5.2. Shot Boundary Recognition Experiment

In order to investigate the performance of the proposed method, we recognize different video shots, especially for gradual shots. The system performance is compared with the multilayer perception network method (MPN method) [36]. We use the original video feature and set the parametersαandγto be the same as before. In the proposed method, we use polynomial kernel, radial basis kernel and linear kernel to build MKSVM and setd=3,  σ2=0.005,  α=1,  β=5,  ρ=0.5, andQ=100. The experimental results are summarized in Figure 4.Figure 4
Comparison of two recognition methods.From Figure4, we found that the above methods can detect not only abrupt cuts but also gradual shots very well, but the proposed method achieves more desired performance than the MPN method for shot boundary recognition. The average precision and recall of the proposed method is up to 94.1% and 91.7%, which is higher by 3.5% and 3.1% than the MPN method, respectively. These results demonstrate that the proposed method is a good tool for shot boundary recognition by using the optimized MKSVM.


### 5.3. Discussion

Two experiments for different type video have been systematically performed, and so now we can conclude the following.(1)
We improve the effect of shot boundary detection in two stages. In the feature extract stage, we use ALPP to extract more useful and discriminating video feature. In the shot boundary detection stage, we use optimized MKSVM obtaining more remarkably boundary detection accuracy.(2)
For feature extraction, the proposed ALPP performed better than LPP and ODP. This is because the former makes use of the label information and model information with adaptive nearest neighbor select strategy. At the same time, the improved weight definition can guarantee that two near points from different modes have a smaller similarity.(3)
Compared with the MPN method, the proposed method can yield better performance on shot boundary recognition. It owes much to the optimized MKSVM, in which the parameters are optimized by the ant colony method. It should be noted that there are some false detection results in the above methods, which may be due to the existence of irregular object movement and the small content change between consecutive frames.


## 5.1. Video Feature Exaction Experiment

In order to testify the effectiveness of the adaptive LPP (ALPP), we extract video feature with ODP, MODP, and ALPP method. For convenience of comparison, we use the same method in paper [35] to detect shot boundary. In the experiment, original video feature is built on color feature, shape feature, and texture feature. Then ODP, MODP, and ALPP method, are used to extract video feature withα=0.5andγ=0.6. In the ODP and MODP methods we adoptknearest neighbor criterion to define the adjacency matrix, in which thekset to 10. The results of performance comparison by using ODP, MODP, and ALPP are shown in Table 1.Table 1
Comparison results between ODP, MODP, and ALPP.
Methods
OPP
MODP
ALPP
Precision
83.7
86.1
89.6
Recall
85.5
87.8
90.4From Table1, we can find that ALPP obtains comparable recognition performance to LPP and ODP with the same shot boundary detect method. In ALPP method, the improved weight definition combines the label information and model information with adaptive nearest neighbor select strategy, which is very important to reflect the data information truthfully. The experiment shows that ALPP has more useful and discriminating ability to extract video feature than others.


## 5.2. Shot Boundary Recognition Experiment

In order to investigate the performance of the proposed method, we recognize different video shots, especially for gradual shots. The system performance is compared with the multilayer perception network method (MPN method) [36]. We use the original video feature and set the parametersαandγto be the same as before. In the proposed method, we use polynomial kernel, radial basis kernel and linear kernel to build MKSVM and setd=3,  σ2=0.005,  α=1,  β=5,  ρ=0.5, andQ=100. The experimental results are summarized in Figure 4.Figure 4
Comparison of two recognition methods.From Figure4, we found that the above methods can detect not only abrupt cuts but also gradual shots very well, but the proposed method achieves more desired performance than the MPN method for shot boundary recognition. The average precision and recall of the proposed method is up to 94.1% and 91.7%, which is higher by 3.5% and 3.1% than the MPN method, respectively. These results demonstrate that the proposed method is a good tool for shot boundary recognition by using the optimized MKSVM.


## 5.3. Discussion

Two experiments for different type video have been systematically performed, and so now we can conclude the following.(1)
We improve the effect of shot boundary detection in two stages. In the feature extract stage, we use ALPP to extract more useful and discriminating video feature. In the shot boundary detection stage, we use optimized MKSVM obtaining more remarkably boundary detection accuracy.(2)
For feature extraction, the proposed ALPP performed better than LPP and ODP. This is because the former makes use of the label information and model information with adaptive nearest neighbor select strategy. At the same time, the improved weight definition can guarantee that two near points from different modes have a smaller similarity.(3)
Compared with the MPN method, the proposed method can yield better performance on shot boundary recognition. It owes much to the optimized MKSVM, in which the parameters are optimized by the ant colony method. It should be noted that there are some false detection results in the above methods, which may be due to the existence of irregular object movement and the small content change between consecutive frames.


## 6. Conclusion

In this paper, we present a new video shot boundary recognition method, which focuses on two key problems: extracting more useful and discriminating feature and improving the accuracy of shot boundary classifier. The major contributions of the paper are to propose an optimized locality preserving present method with model detection and optimized neighbor selection strategy. Meanwhile, an optimized shot boundary classifier based on MKSVM is designed with the ant colony optimization method. Experiments demonstrate that the proposed method is outstanding. The future work is to optimize the other parameters of MKSVM to achieve more desired result.



---

*Source: 353261-2013-11-27.xml*