Content alignment method and system

• US 9,323,865 B2
• Filed: 12/24/2013
• Issued: 04/26/2016
• Est. Priority Date: 12/24/2013
• Status: Active Grant

• Current Assignee: TCL Research America, Inc. (TCL Technology Group Corp.)
• Original Assignee: TCL Research America, Inc. (TCL Technology Group Corp.)
• Inventors: Wang, Haohong, Ding, Hao, Huang, Jia
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US14/139,918
• Publication Number:
  US 20150178369A1
• Time in Patent Office: 854 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: H04N 21/4884 for displaying subtitles

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.

Claims

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

10. The method according to claim 4, wherein the align pair is one of:

a pair of an element of the first content sequence and an element of the second content sequence;

a pair of an element of the first content sequence or the second content sequence and null;

a pair of an element of the first content sequence and a partial sequence of the second content sequence; and

a pair of a partial sequence of the first content sequence and a partial sequence of the second content sequence;

wherein the partial sequence of the first content sequence or the partial sequence of the second content sequence includes a plurality of the selected elements from the first content sequence or a plurality of the selected elements from the second content sequence.

11. The method according to claim 8, wherein:

provided that, the selected elements of the first content sequence are k-level ordered sequence of elements denoted as X, the selected elements of the second content sequence are k-level ordered sequence of elements denoted as Y, X_m=x₁ . . . x_m represents a partial sequence consisting of first m elements in ordered sequence X, X_|X|\m=X−

=x_m+1 . . . x_|X| represents a remaining part of X, Y_n=y₁ . . . y_n represents a partial sequence consisting of first n elements in ordered sequence Y, Y=_|Y|\n=y_n+1 . . . y_|Y| represents a remaining part of Y, dis( ) denotes a distance between two elements, and DIS( ) denotes a total distance of an alignment between two sequences,

a minimum distance among the total distances of alignments between the selected elements of the first content sequence and the second content sequence is obtained by

12. The method according to claim 1, wherein outputting results of the desired alignment further includes:

integrating aligned first content sequence and second content sequence to produce an integrated content sequence based on the desired alignment; and

displaying the integrated content sequence to a user.

13. A content alignment system, comprising:

a memory module;

an output interface; and

a processor coupled to the memory module and the output interface and configured to;

obtain a first content sequence and a second content sequence different from the first content sequence;

represent 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;

determine a desired alignment between the first content sequence and the second content sequence using dynamic programming; and

output results of the desired alignment between the first content sequence and the second content sequence through the output interface;

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.

14. The content alignment system according to claim 13, 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.

15. The content alignment system according to claim 13, 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.

16. The content alignment system according to claim 13, wherein, to determine a desired alignment between the first content sequence and the second content sequence, the processor is further configured to:

determine an align pair for each of selected elements on a same hierarchical level from the first content sequence and the second content sequence;

determine a distance of each align pair as a dissimilarity between the elements in the align pair; and

determine 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.

17. The content alignment system according to claim 16, wherein the processor is further configured to:

determine 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;

determine 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.

18. The content alignment system according to claim 17, 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.

19. The content alignment system according to claim 17, wherein the processor is further configured to:

recursively determine 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

determine 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.

20. The content alignment system according to claim 13, wherein, to output results of the desired alignment, the processor is further configured to:

integrate aligned first content sequence and second content sequence to produce an integrated content sequence based on the desired alignment; and

display the integrated content sequence to a user.