CN105721860B - A kind of Methods for Shot Boundary Detection of Video Sequences based on hypergraph - Google Patents

Abstract

A hypergraph-based video shot boundary detection method: extracting video features; constructing a k-nearest neighbor hypergraph model; finding video shot boundaries, including: setting the minimum score threshold of the score vector according to the k-nearest neighbor hypergraph model; making the label of the query vertex The vector is 1, and the label vectors of other vertices are set to 0; calculate the score vector of each vertex, and record the continuous vertex positions where the score vector is greater than the minimum score threshold, and randomly select half of the vertices as a set, and set the label vector to 1 ;According to the label vector, calculate the score vector of each vertex again; set the label vector of the query vertex to 1, and set the label vector of other vertices to 0 to repeat; determine the boundary and type of the video shot; then make the label vector of the query vertex 1 , the label vectors of other vertices are set to 0 and repeated until the boundaries of all video shots are determined. The invention uses the hypergraph model to retrieve video frames through the hypergraph model, and uses the hypergraph model in the detection field of video shot boundaries.

Description

A Hypergraph-based Video Shot Boundary Detection Method

technical field

The invention relates to a video shot boundary detection method. In particular, it relates to a hypergraph-based video shot boundary detection method that uses the continuity and similarity characteristics of content in the same video shot to analyze the image frames in the video shot through a hypergraph model to determine the boundaries of each shot in the video.

Background technique

A video shot usually refers to a video segment shot continuously by a camera at one time, and a video shot boundary usually refers to a change in a certain sense between adjacent frames of a video shot. Video shot boundary detection is a technique used to find the boundaries between multiple consecutive shots. When two video shots transition, there are usually some noticeable changes, such as changes in color characteristics, etc.

Video shot boundaries generally contain two types. One is an abrupt shot, which refers to a video frame suddenly jumping from one shot to another. Mutation shots usually occur between two frames, and the two frames before and after belong to the two shots before and after. The other is a gradual shot, which refers to the gradual and slow transition of video frames from one shot to another, and the shot will have an editing effect in time and space. Gradient shots usually include fade in and fade out, dissolve, etc. Gradient shots usually occur between a few frames to a dozen frames, and are the transition between the two shots before and after. Among them, the sudden change lens is easier to detect, while the gradual change lens is more difficult to detect, which is the focus of lens boundary detection.

Video shot boundary detection mainly includes three steps: feature extraction of video frames, similarity measurement between video features, and shot boundary determination. The existing video shot boundary detection techniques mainly include edge-based methods and motion information-based methods. The edge and gradient information of the image can well represent the visual information of the image, so it can be used as the feature of the video image. Edge-based video shot detection methods are usually sensitive to camera and object motion, so the detection of progressive shots is not very accurate. The method based on motion information is based on the basic assumption that the video frame in the shot is smooth and the boundary is abrupt. Therefore, the method based on motion information is more accurate for the detection of sudden changes, and it is not very accurate for the detection of gradual changes. The method based on motion information also has the disadvantage of high computational time complexity. At present, the biggest challenge of video shot boundary detection technology is how to detect progressive shots and how to eliminate the impact of lighting or high-speed motion of cameras and objects on video shot boundaries.

Contents of the invention

The technical problem to be solved by the present invention is to provide a hypergraph-based video shot boundary detection method that can determine video shot boundaries one by one by using a hypergraph model.

The technical scheme adopted in the present invention is: a kind of video shot boundary detection method based on hypergraph, comprises the following steps:

1) Extract video features;

2) Construct k-nearest neighbor hypergraph model:

Among them, v represents the vertex of the hypergraph, e represents the hyperedge of the hypergraph, and H(v, e) is the correlation matrix;

3) Find the boundary of the video lens, including:

(1) First, according to the k-nearest neighbor hypergraph model, when a query vertex is given, the score vectors of other vertices relative to the vertex are calculated:

f=(1-γ)(I-γΘ) ^-1 y (2)

Among them, γ is a constant coefficient; I is an identity matrix; y is the label vector of n vertices of the hypergraph, and its dimension is n×1 dimension; f is the score vector relative to the query point, its dimension is n×1 dimension; Θ is n ×n Laplacian matrix, Θ=D _v ^-1/2 HWD _e ^{- 1} H ^T D _v ^-1/2 , where W is the weight matrix, and the weight w(e) of the edge is the diagonal The weight matrix that makes up the hyperedge:

D _v is the degree matrix of the vertex, and the degree matrix of the vertex is formed by taking the degree d(v) of the vertex as the diagonal:

d(v)=∑ _e∈E w(e)·H(v,e) (4)

D _e is the degree matrix of the hyperedge, and the degree matrix of the hyperedge is formed by taking the degree d(e) of the edge as the diagonal:

d(e)= _∑v∈e H(v,e) (5)

(2) Set the minimum score threshold δ of the score vector f;

(3) Let the label vector y(j) of the query vertex=1, and the label vectors of other vertices are set to 0;

(4) Calculate the score vector f of each vertex, and record the continuous vertex positions of f>δ including the jth position, and randomly select the vertices within half of the continuous vertex positions as feedback points, and record them as a set F' _k , and let the label vector y(F' _k )=1, k is the label of the set;

(5) According to the label vector y(F′ _k )=1, calculate the score vector f of each vertex again, and record the continuous vertex positions of f>δ including the set F′ _k , which is recorded as the set F _k , and F _k represents All frames within the same shot containing the jth position;

(6) Let j=F _k (last)+1, k=k+1, set the label vector y(j)=1, calculate the score vector f of each vertex, and record f>δ including the jth position The continuous vertex positions of , and randomly select the vertices within half of the continuous vertex positions as the feedback points, which are recorded as the set F′ _k+1 , and let the label vector y(F′ _k+1 )=1, according to the label Vector y(F′ _k+1 )=1, calculate the score vector f of each vertex again, and record the continuous vertex positions of f>δ including the set F′ _k+1 , and obtain the set F _k+1 , where, F _k ( last) is the last vertex of the set F _k ;

(7) Determine the boundary and type of the video shot;

(8) Set F _k =F _k+1 , return to step (6), until all video shot boundaries are determined.

Step (3) in step 3) represents the label vector y=[0,...,1,...0] ^T of the vertices, where 1 is at the jth position.

Step 3) in step (7) described in determining the boundary of video lens and type include:

Take the intersection F _△ of the set F _k and the set F _k+1 , that is, F _△ ＝F _k ∩F _k+1 , if Then it is determined that the F _k (last) and F _k+1 (first) points are a shot boundary, and the shot boundary is a sudden change shot, that is, the F _k (last) and F _k+1 (first) points are respectively The upper and lower bounds of the mutation lens; if Then it can be determined that the F _△ (first) and F _△ (last) points are a lens boundary, and the lens boundary is a progressive lens, that is, the F _△ (first) and F _△ (last) points are respectively the progressive lens Upper and lower boundaries, where F _k+1 (first) is the first vertex of the set F _k+1 , F _△ (first) is the first vertex of the set F _△ , F _△ (last) is the last of the set F _△ a vertex.

A hypergraph-based video shot boundary detection method of the present invention uses the hypergraph model to retrieve video frames through the hypergraph model, and uses the hypergraph model for the detection field of video shot boundaries, and has the following salient features:

1. The present invention applies the hypergraph model to the shot boundary detection for the first time, and determines the video shot boundary by retrieving all the video frames in a shot, which is different from searching through the change of color or motion information at the shot boundary in the past. The idea of lens boundaries.

2. It is verified by experiments that the present invention can quickly and effectively detect the boundary of video shots, so it is an effective method for detecting the boundary of video shots.

3. The present invention is simple and easy to implement, and has excellent effect. It can be used in the preprocessing stage of video analysis, video summarization, video retrieval and other fields.

Description of drawings

Fig. 1 is the flow chart of the video shot boundary detection method based on hypergraph of the present invention;

Figure 2 is a sudden change shot (the video frame is a continuous video), where 5 frames and 6 frames are respectively the boundaries of the front and back shots;

Fig. 3 is a progressive shot (the video frame is a continuous video), wherein 6 frames to 9 frames are the boundary ranges of the front and rear shots.

detailed description

A hypergraph-based video shot boundary detection method of the present invention will be described in detail below with reference to the embodiments and the accompanying drawings.

A kind of video shot boundary detection method based on hypergraph of the present invention, comprises the steps:

1) Extract video features;

2) Construct k-nearest neighbor hypergraph model:

Among them, v represents the vertex of the hypergraph, e represents the hyperedge of the hypergraph, and H(v, e) is the correlation matrix;

3) Find the boundary of the video lens, including:

(1) First, according to the k-nearest neighbor hypergraph model, when a query vertex is given, the score vectors of other vertices relative to the vertex are calculated:

f=(1-γ)(I-γΘ) ^-1 y (2)

Among them, γ is a constant coefficient; I is an identity matrix; y is the label vector of n vertices of the hypergraph, and its dimension is n×1 dimension; f is the score vector relative to the query point, its dimension is n×1 dimension; Θ is n ×n Laplacian matrix, Θ=D _v ^-1/2 HWD _e ^{- 1} H ^T D _v ^-1/2 , where W is the weight matrix, and the weight w(e) of the edge is the diagonal The weight matrix that makes up the hyperedge:

D _v is the degree matrix of the vertex, and the degree matrix of the vertex is formed by taking the degree d(v) of the vertex as the diagonal:

d(v)=∑ _e∈E w(e)·H(v,e) (4)

D _e is the degree matrix of the hyperedge, and the degree matrix of the hyperedge is formed by taking the degree d(e) of the edge as the diagonal:

d(e)= _∑v∈e H(v,e) (5)

(2) Set the minimum score threshold δ of the score vector f;

(3) Let the label vector y(j) of the query vertex=1, and set the label vector of other vertices to 0, which means the label vector y=[0,…,1,…0] ^T of the vertex, where 1 is at the jth Location;

(4) Calculate the score vector f of each vertex, and record the continuous vertex positions of f>δ including the jth position, and randomly select the vertices within half of the continuous vertex positions as feedback points, and record them as a set F' _k , and let the label vector y(F' _k )=1, k is the label of the set;

(5) According to the label vector y(F′ _k )=1, calculate the score vector f of each vertex again, and record the continuous vertex positions of f>δ including the set F′ _k , which is recorded as the set F _k , and F _k represents All frames within the same shot containing the jth position;

(6) Let j=F _k (last)+1, k=k+1, set the label vector y(j)=1, calculate the score vector f of each vertex, and record f>δ including the jth position The continuous vertex positions of , and randomly select the vertices within half of the continuous vertex positions as the feedback points, which are recorded as the set F′ _k+1 , and let the label vector y(F′ _k+1 )=1, according to the label Vector y(F′ _k+1 )=1, calculate the score vector f of each vertex again, and record the continuous vertex positions of f>δ including the set F′ _k+1 , and obtain the set F _k+1 , where, F _k ( last) is the last vertex of the set F _k ;

(7) Determine the boundaries and types of video shots, including:

Take the intersection F _△ of the set F _k and the set F _k+1 , that is, F _△ ＝F _k ∩F _k+1 , if Then it is determined that the F _k (last) and F _k+1 (first) points are a shot boundary, and the shot boundary is a sudden change shot, that is, the F _k (last) and F _k+1 (first) points are respectively The upper and lower bounds of the mutation lens; if Then it can be determined that the F _△ (first) and F _△ (last) points are a lens boundary, and the lens boundary is a progressive lens, that is, the F _△ (first) and F _△ (last) points are respectively the progressive lens Upper and lower boundaries, where F _k+1 (first) is the first vertex of the set F _k+1 , F _△ (first) is the first vertex of the set F _△ , F _△ (last) is the last of the set F _△ a vertex;

(8) Set F _k =F _k+1 , return to step (6), until all video shot boundaries are determined.

Figure 2 and Figure 3 are examples of judging abrupt shots and progressive shots. Wherein Figure 2 is a sudden change lens, record the result of query point 1 as a set F ₁ ={1,2,3,4,5}; then record the result of query point F ₁ (last)+1 (ie point 6) as a set F ₂ ={6,7,8,9,10}; Then it can be judged that point F ₁ (last)=5 and point F ₂ (first)=6 are the upper and lower bounds of the sudden change lens; Figure 3 is a gradual change lens, and the result of record query point 1 is the set F ₁ ={1,2,3 ,4,5,6,7,8,9}; then record the result of query point F ₁ (last)+1 (namely point 10) as set F ₂ ={6,7,8,9,10,11, 12,13,14}; F _△ ＝F ₁ ∩F ₂ ＝{6,7,8,9}; then it can be determined that point F _△ (first)=6 and point F _△ (last)=9 are the gradient lens Upper and lower bounds.

A video shot boundary detection method based on a hypergraph of the present invention can be divided into coarse-grained range detection and fine-grained range detection during specific implementation. First, determine the approximate range of the video boundary through coarse-grained range detection, which saves a lot of computing time; then, fine-grained range detection is used to refine the boundary range of video shots.

The coarse-grained range detection steps are as follows:

1) Sampling video frames, for example, sampling two frames per second;

2) Extract the features of the video;

3) Construct a k-nearest neighbor hypergraph model;

4) Execute according to the steps of the shot boundary detection method, and judge the shot type and boundary range according to F _△ .

The above coarse-grained detection is only detected between sampling frames, and only a rough range is determined, and then fine-grained range detection is required. Fine-grained range detection includes:

(1) Sampling all video frames between coarse-grained range detection results;

(2) Repeat the coarse-grained range detection steps 2), 3), and 4), so as to obtain the precise boundary range of the video shot.

Claims (2)

1. a kind of Methods for Shot Boundary Detection of Video Sequences based on hypergraph, it is characterised in that comprise the following steps：

1) video features are extracted；

2) k neighbour's hypergraph models are built：

<mrow> <mi>H</mi> <mrow> <mo>(</mo> <mi>v</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> <mo>=</mo> <mfenced open = "{" close = ""> <mtable> <mtr> <mtd> <mrow> <mn>1</mn> <mo>,</mo> </mrow> </mtd> <mtd> <mrow> <mi>i</mi> <mi>f</mi> </mrow> </mtd> <mtd> <mrow> <mi>v</mi> <mo>&amp;Element;</mo> <mi>e</mi> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mn>0</mn> <mo>,</mo> </mrow> </mtd> <mtd> <mrow> <mi>i</mi> <mi>f</mi> </mrow> </mtd> <mtd> <mrow> <mi>v</mi> <mo>&amp;NotElement;</mo> <mi>e</mi> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mrow>

Wherein, v represents the summit of hypergraph, and e represents the super side of hypergraph, and H (v, e) is incidence matrix；

3) video shot boundary is found, including：

(1) first according to k neighbour's hypergraph models, when calculating given inquiry summit, other summits obtain relative to the summit Divide vector：

F=(1- γ) (I- γ Θ)^-1y (2)

Wherein, γ is constant factor；I is unit matrix；Y is the label vector on n summit of hypergraph, and dimension is that n × 1 is tieed up, and f is phase For the score vector of query point, dimension is that n × 1 is tieed up；Θ be n × n Laplacian Matrix, Θ=D_v ^-1/2HWD_e ^-1H^TD_v ^-1/2, Wherein, W is weight matrix, be with while weight w (e) be diagonal is formed surpass while weight matrix：

<mrow> <mi>w</mi> <mrow> <mo>(</mo> <mi>e</mi> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mi>&amp;Sigma;</mi> <mrow> <msub> <mi>v</mi> <mi>i</mi> </msub> <mo>,</mo> <msub> <mi>v</mi> <mi>j</mi> </msub> <mo>&amp;Element;</mo> <mi>e</mi> </mrow> </msub> <mo>|</mo> <mo>|</mo> <msub> <mi>v</mi> <mi>i</mi> </msub> <mo>-</mo> <msub> <mi>v</mi> <mi>j</mi> </msub> <mo>|</mo> <msub> <mo>|</mo> <mn>2</mn> </msub> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>3</mn> <mo>)</mo> </mrow> </mrow>

D_vIt is the degree matrix for being formed summit for diagonal with the degree d (v) on summit for the degree matrix on summit：

D (v)=∑_e∈Ew(e)·H(v,e) (4)

D_eFor the degree matrix on super side, be with while degree d (e) be that diagonal is formed degree matrix when surpassing：

D (e)=∑_v∈eH(v,e) (5)

(2) the minimum score threshold δ of score vector f is set；

(3) label vector y (j)=1 on order inquiry summit, the label vector on other summits are arranged to 0；

(4) each summit score vector f is calculated, and is recorded comprising the f including j-th of position>δ continuous vertex position, and from The summit within half is randomly selected in described continuous vertex position as feedback point, is designated as set F '_k, and make label vector y(F′_k)=1, k is the label of set；

(5) according to label vector y (F '_k)=1, each summit score vector f is calculated again, and record and include set F '_kF>δ Continuous vertex position, be designated as set F_k, now F_kRepresent all frames in the same camera lens comprising j-th of position；

(6) j=F is made_k(last)+1, k=k+1, label vector y (j)=1 is set, calculates each summit score vector f, and record Include the f including j-th of position>δ continuous vertex position, and randomly selected from described continuous vertex position within half Summit as feedback point, be designated as set F '_k+1, and make label vector y (F '_k+1)=1, according to label vector y (F '_k+1)=1, Each summit score vector f is calculated again, and is recorded and included set F '_k+1F>δ continuous vertex position, obtains set F_k+1, Wherein, F_k(last) it is set F_kLast summit；

(7) video shot boundary and type are determined, including：

Take set F_kWith set F_k+1Common factor F_△, i.e. F_△=F_k∩F_k+1IfThen it is determined that in F_kAnd F (last)_k+1 (first) it is a shot boundary at point, and the shot boundary is abrupt shot, i.e. F_kAnd F (last)_k+1(first) point minute Not Wei abrupt shot up-and-down boundary；IfIt can so determine in F_△And F (first)_△(last) it is one at point Shot boundary, and the shot boundary is gradual shot, i.e. F_△And F (first)_△(last) point is respectively the upper and lower of gradual shot Border, wherein, F_k+1(first) it is set F_k+1First summit, F_△(first) it is set F_△First summit, F_△ (last) it is set F_△Last summit；

(8) F is made_k=F_k+1, (6) step is returned to, until all video shot boundaries determine to finish.

A kind of 2. Methods for Shot Boundary Detection of Video Sequences based on hypergraph according to claim 1, it is characterised in that step 3) In (3) step represent summit label vector y=[0 ..., 1 ... 0]^T, wherein 1 j-th of position.