Content alignment method and system

Patent metadata

Field	Value
Publication number	US-9323865-B2
Application number	US-201314139918-A
Country	US
Kind code	B2
Filing date	Dec 24, 2013
Priority date	Dec 24, 2013
Publication date	Apr 26, 2016
Grant date	Apr 26, 2016

Abstract

A method is provided for content alignment. The method includes obtaining a first content sequence and a second content sequence different from the first content sequence. The method also includes representing each of the first content sequence and the second content sequence in a hierarchical structure containing an ordered root element sequence and a sub-tree structure. The ordered root element sequence includes a plurality of root elements and each root element is associated with a sub-tree of elements. The method also includes determining a desired alignment between the first content sequence and the second content sequence using dynamic programming, and outputting results of the desired alignment between the first content sequence and the second content sequence.

First claim

What is claimed is:

1. A method for content alignment, comprising:
obtaining a first content sequence and a second content sequence different from the first content sequence;
representing each of the first content sequence and the second content sequence in a hierarchical structure containing an ordered root element sequence and a sub-tree structure, wherein the ordered root element sequence includes a plurality of root elements and each root element is associated with a sub-tree of elements;
determining a desired alignment between the first content sequence and the second content sequence using dynamic programming; and
outputting results of the desired alignment between the first content sequence and the second content sequence;
wherein:
the hierarchical structure is divided into a plurality of hierarchical levels with a highest level corresponding to the root elements;
each hierarchical level includes one or more ordered sequences of elements;
the one or more ordered sequences of elements are ordered based on one of element locations and element timestamps; and
a K-level element represents a combination of all (K−1)-level subtree elements associated with the K-level element, wherein K is an integer greater than 1, and the (K−1)-level subtree elements is an ordered sequence.

2. The method according to claim 1 , wherein:
the first content sequence and the second content sequence are movie subtitles; and
the hierarchical structure includes three levels of a “paragraph-sentence-word” structure.

3. The method according to claim 1 , wherein:
the first content sequence and the second content sequence are video contents; and
the hierarchical structure includes four levels of a “scene-shot-frame-block” structure wherein a scene is a root element at a highest level and is a combination of one or more ordered shots as subtree elements associated with the scene; a shot is a third-level element and is a combination of one or more ordered frames as subtree elements associated with the shot a frame is a second-level element and is a combination of one or more ordered blocks as subtree elements associated with the frame; and a block is a first-level element.

4. The method according to claim 1 , wherein determining a desired alignment between the first content sequence and the second content sequence further includes:
determining an align pair for each of selected elements on a same hierarchical level from the first content sequence and the second content sequence;
determining a distance of each align pair as a dissimilarity between the elements in the align pair; and
determining a total distance of all align pairs of the selected elements as a total distance of an alignment between the selected elements of the first content sequence and the second content sequence.

5. The method according to claim 4 , further including:
determining a distance of root elements of the first content sequence and the second content sequence;
determining a distance of sub-tree structure elements of the first content sequence and the second content sequence;
determining a total distance of the first content sequence and the second content sequence, as a total distance of an alignment between the first content sequence and the second content sequence, based on the distance of root elements and the distance of sub-tree structure elements.

6. The method according to claim 5 , wherein:
the root elements are represented by vector of features;
the values of the vector are Boolean or normalized real numbers in [0, 1]; and
a Euclidean distance is used as a measurement for a distance between vectors.

7. The method according to claim 5 , further including:
recursively determining the total distances between the first content sequence and the second content sequence to find a minimum distance between the first content sequence and the second content sequence; and
determining an alignment with the minimum distance between the first content sequence and the second content sequence as the desired alignment between the first content sequence and the second content sequence.

8. The method according to claim 4 , wherein:
when the align pair is at a K-level in the hierarchical structure, the dissimilarity between two elements in the align pair are obtained by combining a distance between feature vectors of the two elements of the align pair and a distance between two (K−1)-level subtree sequences associated with the two elements with a desired alignment.

9. The method according to claim 8 , wherein:
provided that a K-level align pair is denoted as (s, t), the distance between feature vectors of the two elements of the align pair is denoted as dis r (K, r(s), r(t)), the distance between two (k−1)-level subtree sequences associated with the two elements with a desired alignment is denoted as DIS(K−1, sub(s), sub(t)), the dissimilarity between two elements in the align pair are obtained by

dis
⁡

(

K
,
s
,
t

)

=

{

dis
r

⁡

(

k
,

r
⁡

(
s
)

,

r
⁡

(
t
)

)

⊕

DIS
⁡

(

k
-
1

,

sub
⁡

(
s
)

,

sub
⁡

(
t
)

Assignees

• Tcl Res America Inc

Inventors

• Ding Hao
• Huang Jia
• Wang Haohong

Classifications

• H04N21/4884

  for displaying subtitles · CPC title

• G06F16/9027 Primary

  Trees · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F17/30961 Primary

  Physics · mapped topic

• G06F17/30327

  Physics · mapped topic