CN101425088A - Key frame extracting method and system based on chart partition - Google Patents

Abstract

The present invention provides a method and system for extracting key frames based on graph segmentation. The method includes the following steps: analyzing video shots, extracting frame features from all video frames in the video shots, and calculating the similarity between images of each frame , and form the intra-shot video frame similarity matrix D _N×N ; apply all the video frames in the shot to build a graph G=(V, E), where each frame in the shot is used as a node of V, node i and node The edge between j is determined by the similarity and positional relationship between the i-th frame and the j-th frame; apply the Normalized Cuts method to the graph G=(V, E) to segment the graph, and divide the graph into several segments; select each segment from the graph and The frame most similar to the other frames in the segment is used as the key frame. The present invention effectively obtains the key frame with stronger expressive ability to the original video shot.

Description

Key frame extraction method and system based on graph segmentation

technical field

The invention relates to the field of video analysis, in particular to a method and system for extracting key frames based on graph segmentation.

Background technique

With the development of image and video processing technology, the amount of media information processed by people is increasing exponentially every day, and the development of information technology has brought massive video data. Media information exchange and application forms such as video on demand, digital interactive TV, and video conferencing have been fully integrated into people's daily work, study, and entertainment. However, the digitized media information, especially the digitized video information has a massive amount of data. Traditional text data analysis and retrieval methods consume a lot of time and manpower when managing video information, and are inefficient. Therefore, how to efficiently and quickly browse and retrieve these video materials has become an increasingly urgent need for people.

A key frame is one or several frames of images that reflect the main information content in a group of shots, and can express the shot content concisely. When video data is needed for retrieval, it is not necessary to search for a video from beginning to end, but to quickly locate the query content through non-linear browsing of key frames.

The current video key frame extraction methods can be mainly divided into three categories. The first method is the specified location method. The specified position method is the simplest keyframe extraction method. This type of method does not consider the specific content of the video and the changing trend of the video, but uses a relatively fixed position as the key frame. For example, after determining the start and end points of the shot, directly take the first frame, the last frame, the middle frame or the frame closest to the average value of all frames as the key frame. Although this technology is simple to operate, fast to calculate, and can obtain key frames in real time, it cannot guarantee that all important segments in the video have at least one key frame, nor can it guarantee that the key frames are representative of the lens content.

The second approach is to analyze where significant content changes occur within a shot. This approach processes video sequences sequentially and only cares about how significantly the video changes along the time axis. The first key frame usually takes the first frame of the lens, traverses all frames in order, and when the change reaches a certain level (reaches the threshold), the frame that reaches the threshold is taken as the next key frame. For example, in the method published in springer's journal Machine Vision and Applications (vol.10, no.2p.51-65, 1997), start looking backward from the previous reference frame until the distance between a frame and the reference frame is greater than the threshold, then Use the previous frame of this frame as the new keyframe. Then search backward from the key frame until the distance between a frame and the new key frame is found to be greater than the threshold, and the previous frame of this frame is used as the next reference frame. The key frame obtained in this way represents all the frames between the previous reference frame and the next reference frame. However, the key frames extracted by this method have a lot to do with the starting position and threshold setting. If the cumulative change method is used, even long videos with small changes will generate many key frames, so the key frames may not be representative of important segments of the video. Moreover, since it is a cumulative change, it is also related to the direction in which the video is processed, and the result obtained by processing the video from back to front is different from that from front to back.

The third method is to divide the frames of the video footage into several categories through cluster analysis, select the point closest to the cluster center to represent the cluster point, and finally form the key frame set of the video sequence. At present, the main clustering methods, such as fuzzy C-means clustering and other methods, have low similarity between clusters and cannot effectively make the similarity within clusters large enough.

In a word, a technical problem that needs to be solved urgently by those skilled in the art is: how to effectively obtain key frames with stronger representation ability for the original video footage.

Contents of the invention

The technical problem to be solved by the present invention is to provide a method and system for extracting key frames based on graph segmentation, which can effectively obtain key frames with stronger representation ability for original video shots.

In order to solve the above problems, the present invention discloses a method for extracting key frames based on graph segmentation, comprising the following steps:

Analyze the video shot, extract the frame features for all the video frames in the video shot, calculate the similarity between the images of each frame, and form the similarity matrix D _{N×N of} the video frame in the shot, where D _ij saves the i-th The comprehensive similarity between the frame and the jth frame;

Apply all the video frames in the shot to build a graph G=(V, E), where each frame in the shot is used as a node of V, and the edge between node i and node j is determined by the similarity between the i-th frame and the j-th frame Determination of degree and position relationship;

Applying the Normalized Cuts method to graph G=(V, E) is segmented, and the graph is divided into several segments;

From each segment in the graph, a frame that is most similar to other frames in said segment is selected as a key frame.

Preferably, the similarity between the two frames of images is calculated by comparing the color histograms of the two frames of images.

Further, the edge between node i and node j in the graph G=(V, E) is determined through the following steps:

Calculate the similarity D _ij of the i-th frame and the j-th frame;

Calculate the position weight between node i and node j $\mathrm{\ω}(i,j)=e^{-\frac{1}{\mathrm{\σ}}{(i-j)}^2},$ where σ is a parameter;

Calculate the edge e(i,j)=ω(i,j)×D _ij between node i and node j.

Preferably, applying the Normally Cuts method to graph G=(V, E) to carry out graph segmentation includes the following steps:

The similarity between two segments V', V" of the definition graph is $\mathrm{cut}(V\′,V\′\′)=\underset{i\∈V\′,j\∈V\′\′}{\overset{\mathrm{no}}{\mathrm{\Σ}}}e(i,j);$

Define the connection index of the graph as $\mathrm{assoc}(x,V)=\underset{i\∈x,j\∈V}{\overset{\mathrm{no}}{\mathrm{\Σ}}}\mathrm{\ω}(i,j);$

Create constraints $\mathrm{Ncut}(V\′,V\′\′)=\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′,V)}+\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′\′,V)};$

Repeat iterations to obtain the global minimum Ncut(V', V"), and obtain the best segmentation of the graph.

Preferably, the color histograms of all video frames in the segment are averaged, and then the video frame closest to the average color histogram is selected as the key frame.

Further, it also includes calculating the weight of the key frame in the shot.

Further, the weight of the key frame in the shot is obtained by the following calculation method:

The number of video frames in the entire shot is NT, and the number of video frames in the current segment is NK;

The weight of the current keyframe in the whole shot is $W=\frac{\mathrm{NK}}{\mathrm{NT}}.$

According to an embodiment of the present invention, a key frame extraction system based on graph segmentation is also disclosed, the system includes:

The video frame similarity matrix calculation module is used to analyze the video shot, extract the frame features of all video frames in the video shot, calculate the similarity between each frame image, and form the video frame similarity matrix D _{N ×} in the shot _N ;

A graph building module, used to set up a graph G=(V, E) using all video frames in the shot, wherein each frame in the shot is used as a node of V;

The edge calculation module between nodes is used to determine the edge between node i and node j according to the similarity and positional relationship between the i-th frame and the j-th frame;

The graph segmentation module is used to segment the graph G=(V, E) using the Normalized Cuts method, and the graph is divided into several sections;

The key frame selection module is used to select a frame most similar to other frames in the segment from each segment in the figure as a key frame, and calculate the weight of the key frame in the shot.

Preferably, the similarity between the two frames of images is calculated by comparing the color histograms of the two frames of images.

Further, the edge calculation module between the nodes includes:

Calculate the submodule of the similarity D _ij of the i-th frame and the j-th frame;

Calculate the position weight between node i and node j $\mathrm{\ω}(i,j)=e^{-\frac{1}{\mathrm{\σ}}{(i-j)}^2}$ The sub-module of , where σ is a parameter;

A submodule that calculates the edge e(i, j)=ω(i, j)×D _ij between node i and node j.

Further, the graph segmentation module includes:

The similarity between two segments V', V" used to define the graph is $\mathrm{cut}(V\′,V\′\′)=\underset{i\∈V\′,j\∈V\′\′}{\overset{\mathrm{no}}{\mathrm{\Σ}}}e(i,j)$ submodule of

The connectivity index used to define the graph is $\mathrm{assoc}(x,V)=\underset{i\∈x,j\∈V}{\overset{\mathrm{no}}{\mathrm{\Σ}}}\mathrm{\ω}(i,j)$ submodule of

used to create constraints $\mathrm{Ncut}(V\′,V\′\′)=\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′,V)}+\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′\′,V)}$ submodule of

It is used for repeated iterations to obtain the global minimum Ncut(V', V"), and obtain the sub-modules for the optimal segmentation of the graph.

Compared with the prior art, the present invention has the following advantages:

The method of the present invention establishes a graph by using frames of video clips, divides the graph by the Normalized Cuts method, and limits the constraint conditions of the segmentation, so as to obtain the optimal division of the graph. The constraints imposed by the application of Normally Cuts for graph segmentation can ensure that there is a large difference between the two segments, and a good similarity within each segment. On each obtained video clip, the frame most similar to other frames is used as a key frame, which can keep a large dissimilarity between key frames; and, the number of video frames in this video clip accounts for the proportion of the entire lens frame number The value is used as the weight of the keyframe on the lens, so that the obtained keyframe expresses the original video more accurately. At the same time, the method of the invention is simple in design and easy to implement.

Description of drawings

Fig. 1 is a kind of key frame extracting method embodiment step flow chart based on graph segmentation of the present invention;

Fig. 2 is a kind of structural block diagram of key frame extraction system based on graph segmentation of the present invention;

FIG. 3 is a schematic diagram of a comparison between the result of extracting key frames from the interview video according to the embodiment of the present invention and the result of extracting key frames using the prior art.

Detailed ways

In order to make the above objects, features and advantages of the present invention more comprehensible, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

Referring to Fig. 1, it shows an embodiment of a key frame extraction method based on graph segmentation of the present invention, which may specifically include:

Step 101, analyze the video shot, extract frame features for all the video frames in the video shot, calculate the similarity between the images of each frame, and form the intra-shot video frame similarity matrix D _N×N , wherein, in D _ij Save the comprehensive similarity between frame i and frame j.

A shot is a set of time-continuous frame sequences, which represent continuous actions in time and space in a scene, corresponding to a recording start-stop operation of the camera, also known as cutting or shooting. A shot is the smallest unit of video data. A scene is a collection of semantically related and temporally adjacent shots.

Preferably, the similarity between the two frames of images can be calculated by comparing the color histograms of the two frames of images.

The color histogram is the most commonly used method to express the color characteristics of an image. Its advantage is that it is not affected by image rotation and translation changes, and it is not affected by image scale changes by further normalization. The color histogram simply describes the global distribution of colors in an image, that is, the proportion of different colors in the entire image, and is especially suitable for describing images that are difficult to automatically segment and images that do not need to consider the spatial position of objects. Generally speaking, the greater the color difference between two frames of images, the smaller the similarity between them, and vice versa.

Step 102, apply all video frames in the shot to establish a graph G=(V, E), wherein each frame in the shot is used as a node of V, and the edge between node i and node j is composed of the i-th frame and the j-th frame The similarity and positional relationship of frames are determined.

An undirected graph G=(V, E) consists of two sets V and E, where V is a finite non-empty set of nodes, and E is a finite set of edges. In the present invention, each frame in the shot is regarded as a node of V. Further, the edge between node i and node j in the graph G=(V, E) is determined through the following steps:

Calculate the similarity D _ij of the i-th frame and the j-th frame;

Calculate the position weight between node i and node j $\mathrm{\ω}(i,j)=e^{-\frac{1}{\mathrm{\σ}}{(i-j)}^2},$ where σ is a parameter;

Calculate the edge e(i,j)=ω(i,j)×D _ij between node i and node j.

Step 103, apply the Normalized Cuts method to graph G=(V, E) to segment, and the graph is divided into several sections, which may specifically include the following steps:

The similarity between two segments V', V" of the definition graph is $\mathrm{cut}(V\′,V\′\′)=\underset{i\∈V\′,j\∈V\′\′}{\overset{\mathrm{no}}{\mathrm{\Σ}}}e(i,j);$

Define the connection index of the graph as $\mathrm{assoc}(x,V)=\underset{i\∈x,j\∈V}{\overset{\mathrm{no}}{\mathrm{\Σ}}}\mathrm{\ω}(i,j);$

Create constraints $\mathrm{Ncut}(V\′,V\′\′)=\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′,V)}+\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′\′,V)};$

Repeat iterations to obtain the global minimum Ncut(V', V"), and obtain the best segmentation of the graph.

Among them, V' and V" are any two segments in V, and the similarity between these two segments is defined as the edge e(i, j ) sum; the connection index assoc(X, V) between segments represents the sum of the position weights of the nodes in X to the points in V; when the value of the constraint condition Ncut(V', V") is the smallest, it is guaranteed to obtain The segmentation of the graph satisfies that the video frames within the segment have a large similarity, and the video frames between the segments have a small similarity, and the best segmentation is obtained at this time.

The Normalized Cuts method is a method based on graph partitioning to establish a similarity measure between nodes, which transforms the graph partitioning problem into a problem of obtaining a suboptimal solution by finding the eigenvalues of the matrix. In the specific segmentation process, the degree of segmentation can be controlled through the establishment of constraint conditions, so as to determine the amount of information carried by each segmented block. This method guarantees the global optimality, so better segmentation results can be obtained. The specific theory of this method is well known to those skilled in the art, so it will not be repeated here. In addition, of course, those skilled in the art can also apply any other feasible mathematical model to segment the graph according to actual needs, so that after segmentation, the video frames in the segment have a relatively large similarity, and the video frames between segments have a small similarity. best split.

Step 104: Select a frame most similar to other frames in the segment from each segment in the image obtained from the optimal segmentation as a key frame.

A key frame is one or several frames of images that reflect the main information content in a group of shots, and can express the contents of the shots concisely.

Preferably, the color histograms of all video frames in the segment are averaged, and then the video frame closest to the average color histogram is selected as the key frame. This method meets two basic requirements for the selection of key frames: the selected frame must be able to reflect the main events in the segment, and the description should be as accurate and complete as possible; the extraction of key frames should be as few and accurate as possible to ensure the amount of data processing It should be as small as possible, and the calculation should not be too complicated. Although in the embodiment of the present invention, the color histogram is used as a feature to extract the key frame, the present invention is not limited to this, other commonly used image comparison algorithms such as direct comparison method, color feature method, texture feature method, shape feature method method, and the image comparison algorithm in the compressed domain, etc. are all within the protection scope of the present invention.

In addition, this step also includes calculating the weight of the keyframe in the shot:

Assuming that the number of video frames in the entire shot is NT, and the number of video frames in the current segment is NK, the weight of the current key frame in the entire shot is $W=\frac{\mathrm{NK}}{\mathrm{NT}}.$ By introducing a weight factor for each key frame, it makes the description of the corresponding video content more accurate and effective.

Applying the method of the present invention, when retrieving the required video material, it is not necessary to search for a section of video from the beginning to the end, but to quickly locate the content of the query through the browsing of key frames, and this method also helps us quickly understand a section of original video. The content of the video to determine whether it is the desired video material.

Referring to FIG. 2 , it shows an embodiment of a key frame extraction system based on graph segmentation of the present invention, which may specifically include:

The video frame similarity matrix calculation module 201 is used to analyze the video shot, extract the frame features for all video frames in the video shot, perform the calculation of the similarity between each frame image, and form the video frame similarity matrix D _N in the shot _×N ;

The graph building module 202 is used to set up a graph G=(V, E) using all the video frames in the shot, wherein each frame in the shot is used as a node of V;

The edge calculation module 203 between nodes is used to determine the edge between node i and node j according to the similarity and positional relationship between the i frame and the j frame;

Figure segmentation module 204, is used for dividing into figure G=(V, E) application Normalized Cuts method, figure is divided into several sections;

The key frame selection module 205 is configured to select a frame most similar to other frames in the segment from each segment in the figure as a key frame, and calculate the weight of the key frame in the shot.

Preferably, the similarity between the two frames of images is calculated by comparing the color histograms of the two frames of images.

Preferably, for one of the implementations of the edge calculation module 203 between nodes, it further includes:

Calculate the submodule of the similarity D _ij of the i-th frame and the j-th frame;

Calculate the position weight between node i and node j $\mathrm{\ω}(i,j)=e^{-\frac{1}{\mathrm{\σ}}{(i-j)}^2}$ The sub-module of , where σ is a parameter;

A submodule that calculates the edge e(i, j)=ω(i, j)×D _ij between node i and node j.

Preferably, for the implementation of the graph segmentation module 204, it further includes:

The similarity between two segments V', V" used to define the graph is $\mathrm{cut}(V\′,V\′\′)=\underset{i\∈V\′,j\∈V\′\′}{\overset{\mathrm{no}}{\mathrm{\Σ}}}e(i,j)$ submodule of

The connectivity index used to define the graph is $\mathrm{assoc}(x,V)=\underset{i\∈x,j\∈V}{\overset{\mathrm{no}}{\mathrm{\Σ}}}\mathrm{\ω}(i,j)$ submodule of

used to create constraints $\mathrm{Ncut}(V\′,V\′\′)=\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′,V)}+\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′\′,V)}$ submodule of

It is used for repeated iterations to obtain the global minimum Ncut(V', V"), and obtain the sub-modules for the optimal segmentation of the graph.

When a key frame extraction system 200 based on graph segmentation of the present invention is specifically implemented, first, the video frame similarity matrix calculation module 201 analyzes the video shots, and extracts frame features from all video frames in the video shots, such as a color histogram Similarity, to calculate the similarity between each frame of images, and form the video frame similarity matrix D _{N × N} in the shot; then, the mapping module 202 will use all the video frames in the shot to establish an undirected graph G=(V , E), wherein each frame in the shot is used as a node of V; the edge calculation module 203 between nodes is used to determine the edge between node i and node j according to the similarity and positional relationship between the i frame and the j frame ;By the graph segmentation module 204, graph G=(V, E) is applied to the Normalized Cuts method to carry out optimal segmentation, and the graph is divided into several sections; at last, utilize the key frame selection module 205 to select and describe the segment from each segment in the graph The frame to which the other frames are most similar is used as a keyframe, and the weight of said keyframe in that shot is calculated.

As for the system embodiment, since it is basically similar to the method embodiment, the description is relatively simple, and for the related parts, please refer to the part of the description of the method embodiment.

Fig. 3(a) is a schematic diagram of three key frames extracted from an interview video in the embodiment of the present invention. The first keyframe extracts frame 60 of the video footage, the second keyframe extracts frame 190 of the video footage, and the third keyframe extracts frame 270 of the video footage. Among them, the interview video contains only one shot with a length of 300 frames. The first part of the shot is a construction worker talking in front of the camera, and the second part of the video turns to the construction site. During this period, there was a relatively big change in the scene in the shot, from the face to the sky to the construction site. Figure 3(b) shows the schematic diagram of the key frame results extracted according to the method proposed in IEEE Transaction on Multimedia (IEEE Transaction on Multimedia, vol.7, no.6p.1097-1105, 2005); the extracted key frame Frames 91, 156, 199, and 258 in the video footage, respectively. At the same time, Fig. 3(c) is a schematic diagram of key frames obtained by random extraction; the extracted key frames are frames 0, 99, 199, and 299 in the video footage, respectively. It can be seen from FIG. 3 that the key frames obtained by applying the method of the present invention can represent the original video shot relatively better, and at the same time, the distance between the key frames is relatively large.

The method and system for extracting key frames based on graph segmentation provided by the present invention have been introduced in detail above. In this paper, specific examples have been used to illustrate the principle and implementation of the present invention. The description of the above embodiments is only for To help understand the method of the present invention and its core idea; at the same time, for those of ordinary skill in the art, according to the idea of the present invention, there will be changes in the specific implementation and scope of application. In summary, the content of this specification It should not be construed as limiting the invention.

Claims (11)

1, a kind of extraction method of key frame of cutting apart based on figure is characterized in that, may further comprise the steps:

Resolve video lens,, carry out calculation of similarity degree between each two field picture, and form frame of video similarity matrix D in the camera lens the feature of all frame of video extraction frames in the video lens _{N * N}, wherein, D _IjMiddle comprehensive similarity of preserving i frame and j frame;

Use all videos frame in the camera lens set up a figure G=(V, E), wherein each frame in the camera lens is as the node of V, the limit between node i and the node j is determined by the similarity and the position relation of i frame and j frame;

(V E) uses Normalized Cuts method and cuts apart, and figure is divided into plurality of sections to figure G=;

From figure, choose a frame the most similar as key frame for every section to other frames in described section.

2, the extraction method of key frame of cutting apart based on figure according to claim 1 is characterized in that, calculates similarity between described two two field pictures by the color histogram of two two field pictures relatively.

3, the extraction method of key frame of cutting apart based on figure according to claim 1 is characterized in that, described figure G=(V, E) limit between middle node i and the node j is determined by following steps:

Calculate the similarity D of i frame and j frame _Ij

Position weight between computing node i and the node j $\mathrm{\ω}(i,j)=e^{-\frac{1}{\mathrm{\σ}}{(i-j)}^2}$ , wherein σ is a parameter;

Limit e between computing node i and the node j (i, j)=ω (i, j) * D _Ij

4, the extraction method of key frame of cutting apart based on figure according to claim 1 is characterized in that, to figure G=(V, E) use Normally Cuts method and carry out figure and cut apart and may further comprise the steps:

Similarity between two segmentation V ', the V ＂ of definition figure is $\mathrm{cut}(V\′,V\′\′)=\underset{i\∈V\′,j\∈V\′\′}{\overset{n}{\mathrm{\Σ}}}e(i,j);$

The connection index of definition figure is $\mathrm{assoc}(X,V)=\underset{i\∈X,j\∈V}{\overset{n}{\mathrm{\Σ}}}\mathrm{\ω}(i,j);$

Set up constraint condition $\mathrm{Ncut}(V\′,V\′\′)=\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′,V)}+\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′\′,V)};$

Iterate, obtain the minimum Ncut of the overall situation (V ', V ＂), obtain optimal segmentation this figure.

5, the extraction method of key frame of cutting apart based on figure according to claim 1 is characterized in that, is averaged by the color histogram with all frame of video in described section, select then with the immediate frame of video of this average color histogram as key frame.

6, the extraction method of key frame of cutting apart based on figure according to claim 1 is characterized in that, also comprises calculating the weight of described key frame in this camera lens.

7, the extraction method of key frame of cutting apart based on figure according to claim 6 is characterized in that, the weight of described key frame in camera lens obtains by following computing method:

Video frame number in the whole camera lens is NT, and the video frame number in the present segment is NK;

The weight of current key frame in whole camera lens is $W=\frac{\mathrm{NK}}{\mathrm{NT}}.$

8, a kind of key-frame extraction system of cutting apart based on figure is characterized in that, comprising:

Frame of video similarity matrix computing module is used to resolve video lens, to the feature of all frame of video extraction frames in the video lens, carries out calculation of similarity degree between each two field picture, and forms frame of video similarity matrix D in the camera lens _{N * N}

Build module, be used to use all videos frame in the camera lens set up a figure G=(V, E), wherein each frame in the camera lens is as the node of V;

Limit computing module between the node is used for according to the similarity of i frame and j frame and the limit between definite node i of position relation and the node j;

Figure is cut apart module, is used for that (V E) uses Normalized Cuts method and cuts apart, and figure is divided into plurality of sections to figure G=;

Key frame is chosen module, is used for choosing a frame the most similar to other frames described section as key frame from every section in figure, and calculates the weight of described key frame in this camera lens.

9, the key-frame extraction system of cutting apart based on figure according to claim 8 is characterized in that, calculates similarity between described two two field pictures by the color histogram of two two field pictures relatively.

10, the key-frame extraction system of cutting apart based on figure according to claim 8 is characterized in that the limit computing module further comprises between the described node:

Calculate the similarity D of i frame and j frame _IjSubmodule;

Position weight between computing node i and the node j $\mathrm{\ω}(i,j)=e^{-\frac{1}{\mathrm{\σ}}{(i-j)}^2}$ Submodule, wherein σ is a parameter;

Limit e between computing node i and the node j (i, j)=ω (i, j) * D _IjSubmodule.

11, the key-frame extraction system of cutting apart based on figure according to claim 8 is characterized in that described figure is cut apart module and further comprised:

The similarity that is used between two segmentation V ', the V ＂ of definition figure is $\mathrm{cut}(V\′,V\′\′)=\underset{i\∈V\′,j\∈V\′\′}{\overset{n}{\mathrm{\Σ}}}e(i,j)$ Submodule;

The connection index that is used for definition figure is $\mathrm{assoc}(X,V)=\underset{i\∈X,j\∈V}{\overset{n}{\mathrm{\Σ}}}\mathrm{\ω}(i,j)$ Submodule;

Be used to set up constraint condition $\mathrm{Ncut}(V\′,V\′\′)=\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′,V)}+\frac{\mathrm{cut}(V\′,V\′\′)}{\mathrm{assoc}(V\′\′,V)}$ Submodule;

Be used to iterate, obtain the minimum Ncut of the overall situation (V ', V ＂), obtain submodule the optimal segmentation of this figure.

Images