Method of grouping images from a video sequence

• US 20060106816A1
• Filed: 09/11/2003
• Published: 05/18/2006
• Est. Priority Date: 09/27/2002
• Status: Active Grant

• Current Assignee: InterDigital Patent Holdings, Inc. (InterDigital, Inc.)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Oisel, Lionel, Chupeau, Bertrand, Le Clerc, Francois
• Granted Patent: US 7,979,435 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44

Abstract

The method utilizing a graph-like structure is comprises the following iteration:

• • calculation of the potential of node n_m, merging of two nodes n_i and n_j, as a function of the distances between the attributes of the key images and as a function of the temporal distance of these key images,
  • calculation of the potential of each edge connecting the merged node to another node of the graph previously connected to nodes n_i or n_j, merging of the two nodes and validation of the new graph if the energy of this graph is less than the energy of the graph before merging.

Claims

1. Method of clustering images of a video sequence consisting of shots and represented by a graph-like structure, a node of the graph representing a shot or a class of shots defined by key images and the nodes being connected by edges, comprising the following iteration:

selection of an edge a_k connecting nodes n_i and n_j

calculation of the potential of node n_m, merging of the two nodes n_i and n_j, as a function of the distances between the attributes of the key images defining the class of shots of node n_i and those of the key images defining the class of shots of node n_j and as a function of the temporal distance of these key images,

calculation of the potential of each edge connecting the merged node to another node of the graph previously connected to nodes n_i or n_j, as a function of the distances between the attributes of the key images defining the class of shots of the merged node and those of the key images defining the class of shots of the other node and as a function of the temporal distance between these key images, the new class of shots associated with the merged node comprising the key images of the classes of shots of the merged nodes,

merging of the two nodes and validation of the new graph if the energy of this graph, which is the sum of the potentials of the nodes and of the edges, is less than the energy of the graph before merging.

2. Method according to claim 1, wherein the graph is initialized by assigning a node to each shot and in that edges are created from one node to another node if the shots relating to these nodes are separated by a predetermined maximum number T of shots.

3. Method according to claim 1, wherein the value of potential associated with the edges and with the nodes is a respectively decreasing and increasing function of temporal distance.

4. Method according to claim 2, wherein the potential of an edge connecting two nodes n_i and n_j is calculated according to the following equation:

$V_a<br><br>\left(n_i,n_j\right)=\underset{I_k\in <br><br>P_i,I_l\in <br><br>P_j}{\min }<br><br>\left(w_{\mathrm{att}}·<br><br>F_a<br><br>\left(K_{\mathrm{att}},{\tilde{d}}_{\mathrm{att}},d_{\mathrm{att}}<br><br>\left(I_k,I_l\right)\right)+w_T·<br><br>F_a<br><br>\left(K_T,{\tilde{d}}_T,d_T<br><br>\left(I_k,I_l\right)\right)\right)$

and in that the potential of a node born from the merging of two nodes ni and nj is defined by the following function;

$V_n<br><br>\left(n_m=n_i\bigcup <br><br>n_j\right)=\underset{I_k\in <br><br>P_i,I_l\in <br><br>P_j}{\min }<br><br>\left(w_{\mathrm{att}}·<br><br>F_n<br><br>\left(K_{\mathrm{att}},{\tilde{d}}_{\mathrm{att}},d_{\mathrm{att}}<br><br>\left(I_k,I_l\right)\right)+w_T·<br><br>F_n<br><br>\left(K_T,{\tilde{d}}_T,d_T<br><br>\left(I_k,I_l\right)\right)\right)$

where;

P_i represents the class of shots associated with node n_i and comprising images I_k

F_a is a decreasing function

F_n is an increasing function

w_att and w_T represent the weights related to attributes and to time

d_att(I_k,I_l) is the distance function associated with the characteristic attributes of the two images

{tilde over (d)}_att represents the mean of the distances between images calculated on the initial graph

d_T(I_k,I_l) is the temporal distance separating the two images

{tilde over (d)}_T is equal to T which represents the temporal threshold

K_att and K_T are two constants.

5. Method according to claim 4, wherein the decreasing function is of the form

$F_a$

( K , d ~ , d ) = 1 1 + ⅇ

K d ~ ⁢

( d - d ~ )

and in that the increasing function is of the form

$F_n<br><br>\left(K,\tilde{d},d\right)=1-\frac{1}{1+{\mathrm{e<br><br>}}^{\frac{K}{\tilde{d}}<br><br>\left(d-\tilde{d}\right)}}$

6. Method according to claim 1, wherein the iterations are stopped as soon as the potential merging of two nodes gives rise to an increase in the energy, the edges being selected, for the calculation of the mergings, in decreasing order of their value of potential.