CN1245697C - Method of proceeding video frequency searching through video frequency segment - Google Patents

Abstract

The present invention relates to a novel method for retrieving videos by video segments, which belongs to the technical field of video retrieval. The existing video segment retrieving method based on contents has the defects of low retrieval precision and low retrieval speed. In view of the defects existing in the prior art, the present invention solves the problem of two segment retrieval difficulty in automatically acquiring similar segments and evaluating the similarity of the two fragments while the optimally matched frame of the graph theory gets down. A weighting bipartite graph model for retrieving segments is established; a similar segment is primarily obtained by inspecting the continuity of similar lenses; the maximum weight match of the segments and the enquiry segments is calculated by using an optimally matched Kuhn_Munkres method; the match is used for judging whether the two segments are similar and determining the boundary of the similar segments; the maximum weight is used for representing the similarity of the two similar fragments. The experimental result indicates that compared with the existing method, the present invention can obtain a high precision ratio and a high recall ratio; meanwhile, the present invention has high retrieval speed.

Description

A kind of method of carrying out video frequency searching by video segment

Technical field

The invention belongs to video search technique area, be specifically related to a kind of method of carrying out video frequency searching by video segment.

Background technology

With image and video information process is that the intelligent information processing technology of core is that people make full use of multimedia messages strong instrument is provided.But, appearance along with extensive image and video database, the data volume that infosystem must be handled increases progressively significantly, how these databases are carried out effective index and become one of bottleneck problem in the multimedia messages process field with retrieval, content-based image and video retrieval method have been opened up new approach for people's head it off.Video clip retrieval is based on the main mode of the video frequency searching of content, and it is meant a given query fragment, finds all fragments similar to it in video library.

Existing fragment search method can be divided into two classes: one, as document " A Framework forMeasuring Video Similarity and Its Application to Video Query byExample " [Y.P.Tan, S.R.Kulkarni, and P.J.Ramadge, IEEEInternational Conference on Image Processing, Vol.2, pp.106-110,1999] described, video segment is divided into the two-layer consideration of fragment-frame, and the similarity utilization of fragment is formed the similarity of its frame and is directly measured.The shortcoming of these class methods is to limit similar fragment must observe same time sequencing, and the practical video program is not observed this constraint, because the result of later stage compilation makes similar fragment may have different camera lens orders fully, difference editor as same advertisement, this comparison based on every frame simultaneously also makes retrieval rate slow.Two, the prior art the most approaching with the present invention is that (author is L.Chen to the document of delivering at IEEE International Conference on Multimedia and Expo calendar year 2001 " A Match and Tiling Approach to Content-based VideoRetrieval ", and T.S.Chua, page number 417-420), this documents discloses a class fragment search method, this method is divided into fragment-camera lens-three layers of consideration of frame to video segment, it comprises such several steps: (1) uses MRA (Temporal Multi-ResolutionAnalysis) method detector lens border earlier, to each frame of each camera lens, carry out color coding and texture coding then.Color coding adopts the average μ and the variances sigma coding of Y component, and texture adopts FRACTAL DIMENSION feature (Fractal Dimension, FD) coding; (2) suppose the similar frame of two camera lens inside, similar according to the time sequencing correspondence, therefore calculate the maximum length sequence of two similar frames of camera lens, the similarity of final two camera lenses is expressed as the linear combination of above-mentioned 3 features, determines similar threshold value σ _L, judge whether two camera lenses are similar; (3) on this basis, use the way of moving window (Sliding Window), finally find the fragment similar to query fragment.This method can accurately be retrieved and similarity retrieval simultaneously, but its problem is: (1) has only considered the quantity of two similar camera lenses of fragment, and the camera lens of not considering multi-to-multi similar (granularity) is to the influence of overall similarity, therefore, even all camera lenses of fragment Y are only similar with the camera lens of fragment X, it is similar to X that Y also can be considered to; (2) hypothesis of Ti Chuing and being false, i.e. the similar frame of two camera lens inside may not be similar according to the time sequencing correspondence; (3) similarity of camera lens is to judge according to two camera lens the longest similar frame sequences, this comparison based on every frame, and the retrieval rate of fragment is slow.

Summary of the invention

At the existing defective of existing video fragment searching method, the objective of the invention is to propose a kind of method of carrying out video frequency searching by video segment, this method can improve precision ratio, recall ratio and the retrieval rate of content-based video clip retrieval on the basis of existing technology greatly, thereby brings into play the huge effect of video clip retrieval technology in current network information society more fully.

The object of the present invention is achieved like this: a kind ofly carry out the method for video frequency searching by video segment, may further comprise the steps:

(1) at first carrying out shot boundary and detect, is the Video Segmentation among query fragment X and the video library Y camera lens;

(2) represent the content of each camera lens then with the first frame of each camera lens; Similar value Similarity (the x of two camera lenses _i, y _j) be the first frame result calculated according to two camera lenses, wherein x _i, y _jRepresent two camera lenses, as Similarity (x _i, y _j)＞T _s, just think two camera lens x _iAnd y _jSimilar, T in the formula _sFor the similar threshold values of camera lens,, retrieve among the video database Y camera lens x with query fragment X according to this formula _iAll similar camera lens y _j

(3) set up the cum rights bipartite graph model that fragment is retrieved,, tentatively be partitioned into the fragment Y similar to query fragment X by investigating the continuity of similar camera lens _k

(4) because Y _kA plurality of fragment Ys similar may have been comprised to X _X, in order further to obtain Y _X, and can estimate Y simultaneously _XWith the similarity of X, adopt the Optimum Matching method to calculate k bipartite graph G _k={ X, Y _k, E _kMaximum weight matching M, from M, obtain Y _X, represent X and Y with this authority simultaneously _XSimilarity.

Specifically, when carrying out video clip retrieval, in step (2), utilize the fragment length constraint setting threshold T of Optimum Matching _s, remove dissimilar camera lens, threshold value T _sBe 0～1, T _sBe preferably 0.71.

Again specifically, when carrying out video clip retrieval, adopt following method tentatively to be partitioned into fragment similar among the video library Y: with camera lens y similar among the Y to X to query fragment X _jBy rank order from small to large, investigate y then _jContinuity, if | y _J+1-y _j|＞2, j=1,2 ..., m-1 then tentatively obtains a fragment Y similar to X _k={ y _i, y _I+1..., y _j, i, j ∈ [1, m].

Further, the constraint condition of use fragment length as previously described filters out T _sThe dissimilar camera lens that brings, realize by twice constraint:

(1), adopts the preceding length constraint of Optimum Matching method: for fear of unnecessary calculating,, fall, if promptly with regard to direct filtration if the fragment length of Yk does not reach requirement Then ignore, wherein, Y _k={ y _i, y _I+1..., y _j, i, j ∈ [1, m], n is the length of query fragment X;

(2), the length constraint after the employing Optimum Matching method: all ω that get the related Optimum Matching M of X _Ij＞0 y, ordering is Y '={ y from small to large _α, y _β... y _γ, α, beta, gamma ∈ [i, j], i, j ∈ [1, m], if

Then ignore.

Again specifically, when carrying out video clip retrieval, because Y _kA plurality of fragment Ys similar may have been comprised to X _X, in order further to obtain Y _X, simultaneously, estimate Y _XWith the similarity of X, the present invention can calculate k bipartite graph G with the Kuhn_Munkres method _k={ X, Y _k, E _kMaximum weight matching M, from M, obtain Y _X, represent X and Y with this authority simultaneously _XSimilarity, the Kuhn_Munkres method of specifically calculating Optimum Matching is as follows:

(1) provides initial label $l\left(x_i\right)=\underset{j}{\max }{\mathrm{\ω}}_{\mathrm{ij}}$ , l (y _j)=0, i, j=1,2..., t, t=max (n, | Y _k|), n is the length of query fragment X, Y _k={ y _i, y _i+ 1 ..., y _j, i, j ∈ [1, m];

(2) obtain limit collection E _l={ (x _i, y _j) | l (x _i)+l (y _j)=ω _Ij, G _l=(X, Y _k, E _l) and G _lIn one the coupling M;

(3) as all nodes of the saturated X of M, then M promptly is the Optimum Matching of G, calculates and finishes, otherwise carry out next step;

(4) in X, look for a M unsaturation point x ₀, make A ← { x ₀, B ← φ, A, B are two set;

(5) if N _Gl(A)=and B, then changeed for (9) step, otherwise carry out next step, wherein, N _Gl(A) Y _k, be with A in the node set of node adjacency;

(6) look for a node y ∈ N _Gl(A)-B;

(7) if y is the M saturation point, then find out the match point z of y, make A ← A ∪ z}, { y} changeed for (5) step, otherwise carries out next step B ← B ∪;

(8) there is one from x ₀But the augmenting path P to y makes M ← M E (P), changes for (3) step;

(9) be calculated as follows the α value: $a=\underset{\underset{y_j\∉N_{G_l}\left(A\right)}{x_i\∈A}}{\min }\{l\left(x_i\right)+l\left(y_j\right)-{\mathrm{\ω}}_{\mathrm{ij}}\},$ Revise label:

Ask E according to l ' _{L '}And G _{L '}

(10) l ← l ', G _l← G _{L '}, changeed for (6) step;

It is function Kuhn_Munkres (X, a Y that the present invention defines the Kuhn_Munkres method _k), so, obtain similar fragment Y _XWith evaluation Y _XBe described below with the method for X similarity:

(1) calls Kuhn_Munkres (X, Y _k), obtain G _k={ X, Y _k, E _kMaximum weight matching M and authority ω;

(2) get all ω of the related M of X _Ij＞0 y, ordering is Y '={ y from small to large _α, y _β..., y _γ, α, beta, gamma ∈ [i, j], in this set, y _α, y _βPossibility is also discontinuous, i.e. y _β-y _α＞1, according to the definition and the Y of front video segment _kMiddle camera lens is all similar in appearance to X, and the present invention gets y _αWith y _γBetween all camera lenses constitute continuous fragment Y _X={ y _α, y _α+1..., y _γ, alpha, gamma ∈ [i, j];

(3) if | Y ' |＜L, then Y _XIgnore, calculate and finish, otherwise carry out next step;

(4) calculate X and Y _XSimilarity $\mathrm{Similarity}(X,Y_X)=\frac{\mathrm{\ω}}{n};$

(5) if | X| 〉=| Y _k|, calculate and finish, otherwise carry out next step;

(6) for | X|＜| Y _k|, at Y _kGet Y _XAfter, see Y _kCan remaining fragment continue to use the Kuhn_Munkres method, if promptly (α-i) 〉=L, Y _k← { y _i, y _I+1, y _α-1, change (1); (if j-γ) 〉=L, Y _k← { y _γ+1, y _γ+2, y _j, change (1);

Get

In above-mentioned (4) step, the present invention uses $\mathrm{Similarity}(X,Y_X)=\frac{\mathrm{\ω}}{n}$ With Similarity (X, Y _X) normalize between [0,1], this value is big more, shows that two fragments are similar more, relatively more existing method, and this formula has succinctly been estimated two maximum similarities that fragment can reach effectively.

Effect of the present invention is: adopt video fragment searching method of the present invention, can obtain higher precision ratio and recall ratio, also obtained retrieval rate faster simultaneously.

Why the present invention has so significant technique effect, its reason is: as described in the previous technique content, the present invention has taken into full account vision and granulometry that the fragment similarity is judged, proposes to obtain with the Kuhn_Munkres method optimization of graph theory Optimum Matching the similarity of similar fragment and two fragments of evaluation.Because video segment is made up of a set of shots, therefore, retrieving is divided into searching lens in the present invention and fragment is retrieved such two stages: 1, on searching lens, the present invention represents that with the first frame of each camera lens the content of each camera lens, this method can improve the speed of fragment retrieval greatly; Simultaneously, in order to ensure the integrality and the correctness of the fragment that retrieval obtains, the present invention proposes to adopt the similar low threshold value of camera lens to ensure recall ratio and the precision ratio that similar camera lens is high simultaneously with fragment length constraint way of combining.2, in the fragment retrieval, set up the cum rights bipartite graph model of fragment retrieval, tentatively obtain similar one by one fragment by the continuity of investigating similar camera lens, use the Kuhn_Munkres method to try to achieve the maximum weight matching of these fragments and query fragment again, coupling be used to judge two fragments whether the phase Sihe determine the border of similar fragment, authority is used to represent the similarity of two similar fragments.The present invention uses the Optimum Matching of graph theory to solve the video frequency searching problem first, this is because the thought of coupling requires similar camera lens corresponding (granularity) one by one, under this condition, the Optimum Matching of obtaining can objectively reflect two number of shots and two degree that the fragment vision is similar that fragment is similar all sidedly, thereby has avoided the granularity problem that camera lens calculates in the existing method.Experimental result shows, compares with existing method with said function, and no matter be precision ratio, recall ratio, or retrieval rate, the present invention has obtained better effect.

Description of drawings

Fig. 1 is the cum rights bipartite graph model synoptic diagram of fragment retrieval;

Fig. 2 is the result for retrieval of the present invention to tennis tournament;

Fig. 3 is the result for retrieval of the present invention to personage's fragment in " black hole ";

Fig. 4 is the result for retrieval of the present invention to the Talks on Focus head.

Embodiment

The present invention is described in further detail below in conjunction with accompanying drawing.

A kind ofly carry out the method for video frequency searching, may further comprise the steps by video segment:

1, at first using space-time section algorithm (spatio-temporal slice) to carry out shot boundary detects, is the Video Segmentation among query fragment X and the video library Y camera lens, can list of references " Video Partitioning by Temporal Slice Coherency " [C.W.Ngo about the detailed description of space-time section algorithm, T.C.Pong, and R.T.Chin, IEEE Transactions on Circuits and Systems forVideo Technology, Vol.11, No.8, pp.941-953, August, 2001];

2, the content of representing each camera lens then with the first frame of each camera lens; Similar value Similarity (the x of two camera lenses _i, y _j) be the first frame result calculated according to two camera lenses, wherein x _i, y _jRepresent two camera lenses, then, setting threshold T of the present invention _s=0.71, as Similarity (x _i, y _j)＞T _s, just think two camera lens x _iAnd y _jSimilar, according to this formula, retrieve among the video database Y camera lens x with query fragment X _iAll similar camera lens y _j

3, set up the cum rights bipartite graph model of fragment retrieval,, tentatively be partitioned into the fragment Y similar to query fragment X by investigating the continuity of similar camera lens _kAs shown in Figure 1, the cum rights bipartite graph model synoptic diagram G={X of fragment retrieval, Y, among the E}, vertex set V=X ∪ Y, X={x ₁, x ₂..., x _nThe expression query fragment, Y={y ₁, y ₂..., y _mThe expression video library, limit collection E={e _Ij, e _IjExpression camera lens x _iWith y _jSimilar, e _IjWeights ω _IjExpression camera lens x _iWith y _jSimilar value.

Suppose query fragment X={x ₁, x ₂..., x _n, video library Y={y ₁, y ₂..., y _m(m＞＞n), x wherein _i, y _jThe expression camera lens, so, the similar camera lens corresponding diagram of X and Y can be expressed as the cum rights bipartite graph G={X in the graph theory, Y, E}, wherein, vertex set V=X ∪ Y, limit collection E={e _Ij, e _IjExpression camera lens x _iWith y _jSimilar, e _IjWeights ω _IjExpression camera lens x _iWith y _jSimilar value, as shown in Figure 1.For video library Y, the camera lens similar to query fragment X is a minority, and a large amount of camera lenses is also dissimilar, is reflected in Fig. 1, i.e. the node y of incidence edge _jBe minority, a large amount of node y _lThe frontier juncture does not join, therefore, and the y of continuous incidence edge _jBetween, generally can be by the y on a plurality of continuous dereferenceds limit _lSeparate.Utilize this character, according to the definition that fragment is made up of cinestrip, the present invention is at first with camera lens y similar to X among the Y _jBy rank order from small to large, investigate y then _jContinuity, if | y _J+1-y _j|＞2, j=1,2 ..., m-1 then tentatively obtains a fragment Y similar to X _k={ y _i, y _I+1..., y _j, i, j ∈ [1, m].

Obtaining fragment Y _kAfter, the present invention adopts the constraint condition of fragment length to remove the dissimilar camera lens that low threshold value is brought.If promptly | Y _k|＜L, then ignore.The present invention gets

N is the length of query fragment X.

4, because Y _kA plurality of fragment Ys similar may have been comprised to X _X, in order further to obtain Y _X, simultaneously, estimate Y _XWith the similarity of X, the present invention uses the Kuhn_Munkres method to calculate k bipartite graph G _k={ X, Y _k, E _kMaximum weight matching M, from M, obtain Y _X, represent X and Y with this authority simultaneously _XSimilarity, the Kuhn_Munkres method of specifically calculating Optimum Matching is as follows:

(1) provides initial label $l\left(x_i\right)=\underset{j}{\max }{\mathrm{\ω}}_{\mathrm{ij}}$ ，l(y _j)＝0，i，j＝1，2...，t，t＝max(n，|Y _k|)；

(2) obtain limit collection E _l={ (x _i, y _j) | l (x _i)+l (y _j)=ω _Ij, G _l=(X, Y _k, E _l) and G _lIn one the coupling M:

(3) as all nodes of the saturated X of M, then M promptly is the Optimum Matching of G, calculates and finishes, otherwise carry out next step;

(4) in X, look for a M unsaturation point x ₀, make A ← { x ₀, B ← φ, A, B are two set;

(5) if N _Gl(A)=and B, then changeed for (9) step, otherwise carry out next step, wherein, N _Gl(A) Y _k, be with A in the node set of node adjacency;

(6) look for a node y ∈ N _Gl(A)-B;

(7) if y is the M saturation point, then find out the match point z of y, make A ← A ∪ z}, { y} changeed for (5) step, otherwise carries out next step B ← B ∪;

(8) there is one from x ₀But the augmenting path P to y makes M ← M E (P), changes for (3) step;

(9) be calculated as follows the α value: $a=\underset{\underset{y_j\∉N_{G_l}\left(A\right)}{x_i\∈A}}{\min }\{l\left(x_i\right)+l\left(y_j\right)-{\mathrm{\ω}}_{\mathrm{ij}}\},$ Revise label:

Ask E according to l ' _{L '}And G _{L '}

(10), l ← l ', G _l← G _{L '}Changeed for (6) step.

It is function Kuhn_Munkres (X, a Y that the present invention defines the Kuhn_Munkres method _k), so, obtain similar fragment Y _XWith evaluation Y _XBe described below with the method for X similarity:

(1) calls Kuhn_Munkres (X, Y _k), obtain G _k={ X, Y _k, E _kMaximum weight matching M and authority ω;

(2) get all ω of the related M of X _Ij＞0 y, ordering is Y '={ y from small to large _α, y _β... y _γ, α, beta, gamma ∈ [i, j], in this set, y _α, y _βPossibility is also discontinuous, i.e. y _β-y _α＞1, according to the definition and the Y of front video segment _kMiddle camera lens is all similar in appearance to X, and the present invention gets y _αWith y _γBetween all camera lenses constitute continuous fragment Y _X={ y _α, y _α+1..., y _γ, alpha, gamma ∈ [i, j];

(3) if | Y ' |＜L, then Y _XIgnore (length constraint after the Kuhn_Munkres method), calculate and finish, otherwise carry out next step;

(4) calculate X and Y _XSimilarity $\mathrm{Similarity}\left(X{,Y}_X\right)=\frac{\mathrm{\ω}}{n};$

(5) if | X| 〉=| Y _k|, calculate and finish, otherwise carry out next step;

(6) for | X|＜| Y _k|, at Y _kGet Y _XAfter, see Y _kCan remaining fragment continue to use the Kuhn_Munkres method, if promptly (α-i) 〉=L, Y _k← { y _i, y _I+1, y _α-1, change (1); (if j-γ) 〉=L, Y _x← { y _γ+1, y _γ+2..., y _j, change (1).

Get In above-mentioned (4) step, the present invention uses $\mathrm{Similarity}(X,Y_X)=\frac{\mathrm{\ω}}{n}$ With Similarity (X, Y _X) normalize between [0,1], this value is big more, shows that two fragments are similar more.Relatively more existing method, this formula has succinctly been estimated two maximum similarities that fragment can reach effectively.

With experimental result the outstanding representation of the present invention in video clip retrieval is described below.Experimental data is several days programs from television recording, this video database is very challenging, always have 3 hours 11 minutes, 4714 camera lenses, 286936 two field pictures, comprised advertisement, news, physical culture, the various types of programs of film, the same video fragment of repetition has been arranged here, as the head of news, advertisement etc.; The similar video segments that a lot of repetitions are also arranged is as same advertisement of the different tennis tournaments in the sports cast, different time length and editor etc.In order to verify validity of the present invention, we have used existing method as the experiment contrast, mainly contain such two reasons: 1, existing method is present given experimental data the best way, also is up-to-date a kind of method; 2, consistent with function of the present invention, can in video library, be partitioned into similar fragment automatically, arrange these similar fragments from high to low by similarity then.In video clip retrieval, except precision ratio and recall ratio, retrieval rate also is a very important index.Relatively more existing method, the present invention has tested the index of retrieval rate first, has compared the retrieval rate of two kinds of methods, and the test machine of use is PIII Dual CPU 1G Hz, internal memory 256M.

Fig. 2, Fig. 3 and Fig. 4 are result for retrieval of the present invention: top delegation is the query fragment that the user submits to, demonstration be the first frame of its each camera lens, be below the retrieval the result, successively arrange according to the order that similarity is successively decreased.First row that retrieves promptly is a query fragment itself, and that yes is the highest for its similarity, and the order that remaining fragment is successively decreased according to similarity is successively arranged.Can see that the fragment that retrieves is all similar with query fragment.Wherein, Fig. 2 is the fragment about tennis tournament; Fig. 3 is about personage's scene in the TV play " black hole "; Fig. 4 is the head of Talks on Focus.Concrete experimental result provides at table 1 and table 2 respectively, it is the same substantially with query fragment accurately to retrieve the fragment of indicating to retrieve in the table 1, have same camera lens and frame sequence, the fragment that similarity retrieval indicates to retrieve in the table 2 only has identical semanteme with query fragment, as tennis tournament, utilize and low-level features such as color are difficult.

Table 1 video segment is the experimental result of retrieval accurately

Query fragment	Frame number	The present invention			Existing method
								Precision ratio	Recall ratio	Speed (second)	Precision ratio	Recall ratio	Speed (second)

1, the head of news	832	100％	100％	9	75％	100％	230
								2, football news	715	100％	100％	11	100％	100％	196
3, Huiyuan's advertisement	367	100％	100％	21	33.3％	100％	97
								4, bright advertisement	374	100％	100％	11	100％	100％	101
5, good fortune advertisement near the house	432	100％	100％	13	100％	100％	116
								On average	544	100％	100％	13	81.7％	100％	148

The experimental result of table 2 video segment similarity retrieval

Query fragment	Frame number	The present invention			Existing method
								Precision ratio	Recall ratio	Speed (second)	Precision ratio	Recall ratio	Speed (second)
		1, tennis tournament	507	100％	50％	5	100％							50％	140
2, the doctor gives emergency treatment to a patient	1806							100％	50％	13	50％	50％	507
		3, TCL advertisement	374	100％	100％	12	85.7％							100％	100
4, melatonin advertisement	374							100％	75％	17	100％	100％	100
		5, Amoisonic's advertisement	374	80％	100％	15	100％							50％	99
On average	687							96％	75％	12	87.1％	70％	189

No matter can see from table 1 and table 2, be precision ratio, or recall ratio, and the present invention is better than existing method.Main cause is that existing method only calculates the quantity of two similar camera lenses of fragment, and the present invention has considered the corresponding relation of similar camera lens.In addition, great advantage of the present invention is embodied on the retrieval rate of fragment, according to our experiment, basically be to equal the time that similar camera lens is judged total retrieval time, existing method adopts the way that compares frame by frame in chronological order, and the present invention only need compare the first frame of each camera lens, so the present invention is far away faster than existing method, fast order of magnitude can satisfy the demand of real-time retrieval basically.

Claims (6)

1, a kind ofly carry out the method for video frequency searching, may further comprise the steps by video segment:

(1) at first carrying out shot boundary and detect, is the Video Segmentation in query fragment and the video library camera lens;

(2) represent the content of each camera lens then with the first frame of each camera lens; Similar value Similarity (the x of two camera lenses _i, y _j) be the first frame result calculated according to two camera lenses, wherein x _i, y _jRepresent two camera lenses, as Similarity (x _i, y _j)＞T _s, just think two camera lens x _iAnd y _jSimilar, T in the formula _sFor the similar threshold value of camera lens,, retrieve among the video database Y camera lens x with query fragment X according to this formula _iAll similar camera lens y _j

(3) set up the cum rights bipartite graph model that fragment is retrieved,, tentatively be partitioned into the fragment Y similar to query fragment X by investigating the continuity of similar camera lens _k

(4) because Y _kA plurality of fragment Ys similar may have been comprised to X _X, in order further to obtain Y _X, and can estimate Y simultaneously _XWith the similarity of X, adopt the Optimum Matching method to calculate k bipartite graph G _k={ X, Y _k, E _kMaximum weight matching M, from M, obtain Y _X, represent X and Y with this authority simultaneously _XSimilarity.

2, as claimed in claim 1ly a kind ofly carry out the method for video frequency searching, it is characterized in that: in step (2), utilize the fragment length constraint setting threshold T of Optimum Matching by video segment _s, remove dissimilar camera lens, threshold value T _sBe 0～1.

3, as claimed in claim 2ly a kind ofly carry out the method for video frequency searching, it is characterized in that: threshold value T by video segment _s=0.71.

4, as claimed in claim 1ly a kind ofly carry out the method for video frequency searching, it is characterized in that in step (3), adopt following method tentatively to be partitioned into fragment similar among the video library Y: camera lens y similar among the Y to X to query fragment X by video segment _jBy rank order from small to large, investigate y then _jContinuity, if | y _J+1-y _j|＞2, j=1,2 ..., m-1 then tentatively obtains a fragment Y similar to X _k={ y _i, y _I+1..., y _j, i, j ∈ [1, m].

5, as claimed in claim 2ly a kind ofly carry out the method for video frequency searching, it is characterized in that using the constraint condition of fragment length to filter out T by video segment _sThe dissimilar camera lens that brings, realize by twice constraint:

(1), adopts the preceding length constraint of Optimum Matching method: for fear of unnecessary calculating, if Y _kFragment length do not reach requirement, fall with regard to direct filtration, if promptly

Then ignore, wherein, Y _k={ y _i, y _I+1..., y _j, i, j ∈ [1, m], n is the length of query fragment X;

(2), the length constraint after the employing Optimum Matching method: all ω that get the related Optimum Matching M of X _Ij＞0 y, ordering is Y '={ y from small to large _α, y _β..., y _γ, α, beta, gamma ∈ [i, j], if

Then ignore.

6, describedly a kind ofly carry out the method for video frequency searching by video segment as claim 1 or 5, it is characterized in that in the step (4), the Optimum Matching method is the Kuhn_Munkres method, this method is as follows:

(1) provides initial label $l\left(x_i\right)=\underset{j}{\max }{\mathrm{\ω}}_{\mathrm{ij}},$ L (y _j)=0, i, j=1,2 ..., t, and t=max (n, | Y _k|), n is the length of query fragment X, Y _k={ y _i, y _I+1..., y _j, i, j ∈ [1, m];

(2) obtain limit collection E _l={ (x _i, y _j) | l (x _i)+l (y _j)=ω _Ij, G _l=(X, Y _k, E _l) and G _lIn one the coupling M;

(3) as all nodes of the saturated X of M, then M promptly is the Optimum Matching of G, calculates and finishes, otherwise carry out next step;

(4) in X, look for a M unsaturation point x ₀, make A ← { x ₀, B ← φ, A, B are two set;

(5) if $N_{G_l}\left(A\right)=B,$ Then changeed for (9) step, otherwise carry out next step, wherein, N _Gl(A) Y _k, be with A in the node set of node adjacency;

(6) look for a node y ∈ N _Gl(A)-B;

(7) if y is the M saturation point, then find out the match point z of y, make A ← A ∪ z}, { y} changeed for (5) step, otherwise carries out next step B ← B ∪;

(8) there is one from x ₀But the augmenting path P to y makes M ← M E (P), changes for (3) step;

(9) be calculated as follows a value: $a=\underset{\underset{y_j\∉N_{G_l}}{x_i\∈A}}{\min }\{l\left(x_i\right)+l\left(y_j\right)-\mathrm{\ω}\},$ Revise label:

Ask E according to l ' _{L '}And G _{L '}

(10) l ← l ', G _l← G _{L '}, changeed for (6) step;

Definition Kuhn_Munkres method is function Kuhn_Munkres (X, a Y _k), so, obtain similar fragment Y _XWith evaluation Y _XBe described below with the method for X similarity:

(1) calls Kuhn_Munkres (X, Y _k), obtain G _k={ X, Y _k, E _kMaximum weight matching M and authority ω;

(2) get all ω of the related M of X _Ij＞0 y, ordering is Y '={ y from small to large _α, y _β..., y _γ, α, beta, gamma ∈ [i, j], in this set, y _α, y _βPossibility is also discontinuous, i.e. y _β-y _α＞1, according to the definition and the Y of front video segment _kMiddle camera lens is all similar in appearance to X, and the present invention gets y _αWith y _γBetween all camera lenses constitute continuous fragment Y _X={ y _α, y _α+1..., y _γ, alpha, gamma ∈ [i, j], i, j ∈ [1, m];

(3) if | Y ' |＜L, then Y _XIgnore, calculate and finish, otherwise carry out next step;

(4) calculate X and Y _XSimilarity $\mathrm{Similarity}(X,Y_X)=\frac{\mathrm{\ω}}{n};$

(5) if | X| 〉=| Y _k|, calculate and finish, otherwise carry out next step;

(6) for | X|＜| Y _k|, at Y _kGet Y _XAfter, see Y _kCan remaining fragment continue to use the Kuhn_Munkres method, if promptly (α-i) 〉=L, Y _k← { y _i, y _I+1, y _α-1, change (1); (if j-γ) 〉=L, Y _k← { y _γ+1, y _γ+2..., y _j, change (1);

Get In above-mentioned (4) step, the present invention uses $\mathrm{Similarity}(X,Y_X)=\frac{\mathrm{\ω}}{n}$ With Similarity (X, Y _X) normalize between [0,1], this value is big more, shows that two fragments are similar more.

Images