Patent US7613365B2 successfully refreshed from Google Patents.
US7613365B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Video summarization system and the method thereof
Assignee: National Cheng Kung University
•
Filing: 2006-07-14
•
Granted: 2009-11-03
•
Expires: 2026-07-14
Abstract
Abstract The present invention discloses a video summarization system and the method thereof. A similarity computing apparatus computes the similarity between each frame to obtain multiple similarity values. A key frame extracting apparatus chooses the key frames from the frames wherein the sum of the similarity values between the key frames is a minimum. A feature space mapping apparatus converts the sentences into multiple corresponding sentence vectors and computes the distance between each sentence vector to obtain multiple distance values. A clustering apparatus divides the sentences into multiple clusters according to the distance values and the importance of the sentences, and also applies a splitting step to split the cluster with the highest importance into multiple new clusters. A key sentence extracting apparatus chooses multiple key sentence from the clusters, wherein the sum of the importance of the key sentences is the maximum.
Inventors
- 👤 Jhing-Fa Wang
- 👤 Jia-Ching Wang
- 👤 Chen-Yu Chen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:20
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/70; G06F16/78; G06F16/783; G06F16/7844; G06V; G06V20/00; G06V20/40; G06V20/46; G06V20/47; G06F16/73; G06F16/738; G06F16/739; G06F16/7847; G06F16/785; Y; Y10; Y10S; Y10S345/00; Y10S345/949; Y10S345/95; Y10S345/951
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
260 words
A video summarization method comprising: providing a video wherein the video has a plurality of sentences and a plurality of frames; applying a key frame extraction step to the frames of the video to acquire a plurality of key frames, wherein the key frame extraction step comprises: computing the similarity between each frame to obtain a plurality of similarity values; and choosing the key frames from the frames, wherein the sum of the similarity values between the key frames is the minimum; applying a key sentence extraction step to the sentences of the video to acquire a plurality of key sentences, wherein the key sentence extraction step comprises: converting the sentences into a plurality of corresponding sentence vectors; computing the distance between each sentence vector to obtain a plurality of distance values; according to the distance values, dividing the sentences into a plurality of clusters, wherein the clusters are members of a set; computing the importance of each sentence of each cluster to obtain the importance of each cluster; applying a splitting step to split a most important member with the highest importance in the cluster into a plurality of new clusters, wherein the new clusters replace the original most important member and join the set as members of the set; repeating the splitting step until the number of the clusters reaches a predetermined value; and choosing at least one key sentence from each members of the set, wherein the sum of the importance of the key sentences is the maximum; and outputting the key frames and the key sentences.
Claim 2
Dependent Claim
260 words
A video summarization method comprising: providing a video wherein the video has a plurality of sentences and a plurality of frames; applying a key frame extraction step to the frames of the video to acquire a plurality of key frames, wherein the key frame extraction step comprises: computing the similarity between each frame to obtain a plurality of similarity values; and choosing the key frames from the frames, wherein the sum of the similarity values between the key frames is the minimum; applying a key sentence extraction step to the sentences of the video to acquire a plurality of key sentences, wherein the key sentence extraction step comprises: converting the sentences into a plurality of corresponding sentence vectors; computing the distance between each sentence vector to obtain a plurality of distance values; according to the distance values, dividing the sentences into a plurality of clusters, wherein the clusters are members of a set; computing the importance of each sentence of each cluster to obtain the importance of each cluster; applying a splitting step to split a most important member with the highest importance in the cluster into a plurality of new clusters, wherein the new clusters replace the original most important member and join the set as members of the set; repeating the splitting step until the number of the clusters reaches a predetermined value; and choosing at least one key sentence from each members of the set, wherein the sum of the importance of the key sentences is the maximum; and outputting the key frames and the key sentences.
Claim 3
Dependent Claim
32 words
The video summarization method according to claim 1 , further comprising dividing the frames of the video into a plurality of segments before the step of computing the similarity between each frame.
Claim 4
Dependent Claim
37 words
The video summarization method according to claim 2 , wherein the step of dividing the frames of the video into the segments is based on shots of the video or a unit of length of the video.
Claim 5
Dependent Claim
43 words
The video summarization method according to claim 1 , wherein the step of computing the similarity between each frame uses an algorithm and the algorithm is selected from the group consisting of a color histogram similarity algorithm and a mutual information similarity algorithm.
Claim 6
Dependent Claim
20 words
The video summarization method according to claim 1 , further comprising composing the key frames to form an abstract video.
Claim 7
Dependent Claim
43 words
The video summarization method according to claim 5 , further comprising choosing the key frames in accordance with a predetermined compression ratio wherein the predetermined compression ratio is the ratio of the length of the abstract video to the length of the video.
Claim 8
Dependent Claim
75 words
The video summarization method according to claim 1 , wherein the step of choosing the key frames is based on a maximum difference measure (MDM) algorithm comprising: computing the sums of the similarity values, respectively, to obtain a plurality of operation results; finding a minimum value from the operation results; and according to the minimum value, finding the similarity values resulting in the minimum value and further determining the key frames having the similarity values.
Claim 9
Dependent Claim
144 words
The video summarization method according to claim 7 , wherein the step of computing the sums of the similarity values, respectively, to obtain the operation results is based on an equation: S A ( u + 1 , v ) = min i { S A ( u , i ) + S ( i , v ) } , v - 1 ≤ i ≤ V - U + u , where v represents the index of the frames, V represents the number of the frames, u represents the index of the key frames, U represents the number of the key frames, S A (u+1,v) represents one of the operation results, S A (u,i) represents the sum of part of the similarity values, and S(i,v) represents the similarity between the ith frame and the vth frame of the frames.
Claim 10
Dependent Claim
59 words
The video summarization method according to claim 8 , wherein the step of finding the minimum value from the operation results is in accordance with an equation: S Best = min v [ S A ( U , v ) ] , where S Best represents the minimum value and S A (U,v) represents the operation results.
Claim 11
Dependent Claim
30 words
The video summarization method according to claim 1 , further comprising mapping the sentences to a feature space before the step of converting the sentences into the corresponding sentence vectors.
Claim 12
Dependent Claim
51 words
The video summarization method according to claim 1 , wherein the step of dividing the sentences into the clusters uses a clustering algorithm and the clustering algorithm is selected from the group consisting of a K-means clustering algorithm, a LBG algorithm, a support vector clustering algorithm and a neural network algorithm.
Claim 13
Dependent Claim
42 words
The video summarization method according to claim 1 , wherein the step of computing the importance of each sentence of each cluster is based on the frequency of each term in the sentences and the location of the sentences in the video.
Claim 14
Dependent Claim
87 words
The video summarization method according to claim 12 , wherein the step of computing the importance of each sentence of each cluster computes the inverse document frequency (IDF) of each term in the sentences multiplied by a term weight in accordance with the following equation: IMP = ∑ j ∑ k g jk × IDF ( t k , s j ) , where s j represents the sentences, t k represents the term in the sentences and g jk represents the term weight.
Claim 15
Dependent Claim
90 words
The video summarization method according to claim 13 , wherein the term weight is based on the following equation: g jk = { c , if t k both occurs in s j and in the first three sentences 1 , if t k only occurs in s j 0 , otherwise where c is greater than 1.
Claim 16
Dependent Claim
34 words
The video summarization method according to claim 1 , further comprising computing the importance of each sentence of the new clusters to obtain the importance of each new clusters after applying the splitting step.
Claim 17
Dependent Claim
27 words
The video summarization method according to claim 1 , further comprising applying a judging step to determine whether the number of the clusters reaches the predetermined value.
Claim 18
Dependent Claim
32 words
The video summarization method according to claim 1 , further comprising outputting the key frames and the key sentences to a browsing interface to present the key frames and the key sentences.
Claim 19
Dependent Claim
22 words
The video summarization method according to claim 1 , wherein the key sentences are centroid sentences of the members of the set.
Claim 20
Dependent Claim
243 words
A video summarization system, suitable for extracting a plurality of key frames and a plurality of key sentences from a video to form an abstract wherein the video comprises a plurality of sentences and a plurality of frames, the video summarization system comprising: a similarity computing apparatus, used for computing the similarity between each frame to obtain a plurality of similarity values; a key frame extracting apparatus, used for choosing the key frames from the frames wherein the sum of the similarity values between the key frames is minimum; a feature space mapping apparatus, used for converting the sentences into a plurality of corresponding sentence vectors and computing the distance between each sentence vector to obtain a plurality of distance values; a clustering apparatus, used for dividing the sentences into a plurality of clusters according to the distance values wherein the clusters are members of a set, and the clustering apparatus further computing the importance of each sentence of each cluster to obtain the importance of each cluster and applying a splitting step to split a most important member with the highest importance in the cluster into a plurality of new clusters, wherein the new clusters replace the original most important member and join the set as members of the set; and a key sentence extracting apparatus, used for choosing at least one key sentence from each members of the set, wherein the sum of the importance of the key sentences is maximum.
Claim 21
Dependent Claim
243 words
A video summarization system, suitable for extracting a plurality of key frames and a plurality of key sentences from a video to form an abstract wherein the video comprises a plurality of sentences and a plurality of frames, the video summarization system comprising: a similarity computing apparatus, used for computing the similarity between each frame to obtain a plurality of similarity values; a key frame extracting apparatus, used for choosing the key frames from the frames wherein the sum of the similarity values between the key frames is minimum; a feature space mapping apparatus, used for converting the sentences into a plurality of corresponding sentence vectors and computing the distance between each sentence vector to obtain a plurality of distance values; a clustering apparatus, used for dividing the sentences into a plurality of clusters according to the distance values wherein the clusters are members of a set, and the clustering apparatus further computing the importance of each sentence of each cluster to obtain the importance of each cluster and applying a splitting step to split a most important member with the highest importance in the cluster into a plurality of new clusters, wherein the new clusters replace the original most important member and join the set as members of the set; and a key sentence extracting apparatus, used for choosing at least one key sentence from each members of the set, wherein the sum of the importance of the key sentences is maximum.
Claim 22
Dependent Claim
23 words
The video summarization system according to claim 19 , further comprising a browsing interface to present the key frames and the key sentences.
Claim 23
Dependent Claim
50 words
The video summarization system according to claim 19 , wherein the clustering apparatus uses a clustering algorithm to apply the splitting step and the clustering algorithm is selected from the group consisting of a K-means clustering algorithm, a LBG algorithm, a support vector clustering algorithm and a neural network algorithm.
Claim 24
Dependent Claim
45 words
The video summarization system according to claim 19 , wherein the clustering apparatus applies the step of computing the importance of each sentence of each cluster based on the frequency of each term in the sentences and the location of the sentences in the video.
Claim 25
Dependent Claim
94 words
The video summarization system according to claim 22 , wherein the clustering apparatus applies the step of computing the importance of each sentence of each cluster based on computing the inverse document frequency (IDF) of each term in the sentences multiplied by a term weight and in accordance with the following equation: IMP = ∑ j ∑ k g jk × IDF ( t k , s j ) , where s j represents the sentences, t k represents the term in the sentences and g jk represents the term weight.
Claim 26
Dependent Claim
90 words
The video summarization system according to claim 23 , wherein the term weight is based on the following equation: g jk = { c , if t k both occurs in s j and in the first three sentences 1 , if t k only occurs in s j 0 , otherwise where c is greater than 1.
Claim 27
Dependent Claim
37 words
The video summarization system according to claim 19 , further comprising computing the importance of each sentence of the new clusters to obtain the importance of each new clusters after the clustering apparatus proceeding the splitting step.
Claim 28
Dependent Claim
31 words
The video summarization system according to claim 19 , wherein the clustering apparatus further comprises applying a judging step to determine whether the number of the clusters reaches a predetermined value.
Claim 29
Dependent Claim
22 words
The video summarization system according to claim 19 , wherein the key sentences are centroid sentences of the members of the set.
References Cited (Backward Citations)
US7296009B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2012-11-02 | 2013-05-04 | 2013-11-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2016-11-02 | 2017-05-04 | 2017-11-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2020-11-02 | 2021-05-04 | 2021-11-03 | $7700.00 | Window Closed / Lapsed |