Method and apparatus for representing and editing multimedia compositions using a tree structure

• US 5,724,605 A
• Filed: 03/31/1995
• Issued: 03/03/1998
• Est. Priority Date: 04/10/1992
• Status: Expired due to Term

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Avid Technology Incorporated
• Inventors: Wissner, Michael J.
• Primary Examiner(s): Burwell, Joseph R.
• Application Number:
  US08/415,091
• Time in Patent Office: 1,068 Days
• Field of Search: 395/153, 395/154, 395/155, 395/160, 395/161, 395/600, 395/806, 395/807, 395/615, 360/18, 360/19.1
• US Class Current: 715/202
• CPC Class Codes: G11B 2220/90 Tape-like record carriers
• CPC Class Codes: G11B 27/024 on tapes G11B27/028, G11B27/029 take precedence
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: G11B 27/34 Indicating arrangements indicating means incorporated in magazine or cassette G11B23/046 and G11B23/0875; indicating measured values in general G01D
• CPC Class Codes: H04N 21/23412 for generating or manipulating the scene composition of objects, e.g. MPEG-4 objects
• CPC Class Codes: H04N 21/44012 involving rendering scenes according to scene graphs, e.g. MPEG-4 scene graphs
• CPC Class Codes: H04N 5/262 Studio circuits, e.g. for mixing, switching-over, change of character of image, other special effects ; Cameras specially adapted for the electronic generation of special effects

Abstract

A system for editing and representing multimedia compositions in which the representation of a composition enables a composition to be an arbitrarily deep nesting of assemblies of components. In this representation, relationships between synchronous components may be represented, by an array or list. Components which are related sequentially in time are represented by a sequence component, which may be implemented as a tree. For the purpose of improving searching within the tree, a sequence component is implemented as a balanced binary, or 2-3-tree. By using such a representation, searching for a component based on its position in time in the sequence may be performed in logarithmic rather than linear time. Each node in the tree has a corresponding duration, which represents the sum of the durations of any subnodes. Media data for a composition is excluded from the representational structures and is merely referred to by such structures. Thus, compositions may be stored separately from the media data.

Claims

1. A computer system for representing a multimedia composition, comprising:

means for defining a component by reference to a plurality of samples of media data at a temporal sampling resolution;

means for defining a sequence as an ordered collection of components, wherein the components occur sequentially in the multimedia composition, wherein the ordered collection is ordered using a search tree, wherein the search tree has a root node with a key indicative of the total duration of the sequence and nodes including subnodes of the root node and subnodes of other nodes, wherein each node has a key indicative of the total duration of any subnodes of the node and leaves, wherein the leaves of the search tree are the components in the sequence; and

means for defining the multimedia composition as a collection of sequences, wherein the sequences occur concurrently in the multimedia composition.

2. The system of claim 1, wherein a component is defined using both a reference to other components defining the component and a reference to an alternate version of material represented by the component.

3. The system of claim 2, wherein the alternate version of material represented by a component is a reference to a single clip resulting from a combination of the other components defining the component.

4. The system of claim 1, wherein a representation of a component includes an indication of a player function code which indicates processing to be performed on the component when the component is presented by a player.

5. The system of claim 4, wherein a component includes a track type code, and the system includes means, responsive to editing functions, for ensuring, that all components in a sequence on a track are of a same type and means for ensuring that each track in a track group has a type consistent with the player function code and a position of the track in the track group.

6. The system of claim 1, wherein each component in the composition has a virtual sample rate and an actual sample rate, stored for each component, and wherein each component stores a length measured in virtual sample rate units to enable a determination of actual time duration represented by the component.

8. The system of claim 1, wherein a source clip stores both a reference to digitized media and a reference to an analog source for the digitized media.

9. The system of claim 8, wherein the source clip is defined using start location and a stop location in a source of media data.

10. The system of claim 8, wherein the source clip contains an indication of a start location and a duration for the digitized media.

11. The system of claim 10, wherein the start location is in virtual sample rate units.

12. The system of claim 11, wherein the start location is relative to an origin on the analog source.

13. The system of claim 1, wherein at least one component represents a transition between two components in the sequence and wherein the representation of a transition includes a code indicating a transition effect and a location of a boundary between the two components without the transition effect.

14. The system of claim 13, further comprising means, operative when a transition is removed during editing, for restoring the representation of the multimedia composition to a state without the transition effect by creating a sequence of the two components with the stored location of the boundary as a boundary between the two components.

15. The system of claim 14, further comprising means for playing the transition without performing the transition effect and for displaying on a display the two components sequentially with a cut defined by the location of the boundary included in the representation of the transition.

16. The system of claim 1, wherein the search tree is a 2-3 search tree.

17. The system of claim 16, wherein the search tree is a binary search tree.

18. A method for representing a sequence in a multimedia composition containing a plurality of components defined by reference to a plurality of samples of media data at a temporal sampling resolution, comprising the steps of:

selecting a first sequence of a plurality of components to be presented sequentially in the multimedia composition;

determining a total duration for each group of sequentially adjacent components and iteratively determining total durations for groups of the groups; and

storing an indication of the first sequence, including storing an indication of a search tree having leaves indicative of the components, nodes representing the groups of sequentially adjacent components and groups of groups, each node having a key defined by the total duration of group represented by the node and a root node representing the sequence and having a key defined by the total duration of the sequence.

19. A computer system for manipulating a representation of a multimedia composition containing a sequence of components, comprising:

a computer-readable medium;

digital logic stored on the computer-readable medium and defining a representation using an indication of a tree having a plurality of leaves, wherein each leaf of the plurality of leaves of the tree represent components to be placed in the composition and each having a duration, and wherein the tree relating the components has a plurality of nodes, each node having a plurality of subnodes, and wherein each node stores a value indicative of a total duration of all subnodes and leaves oft he node, whereby a root node stores a value indicative of a total duration of the sequence; and

means for locating a component at a desired temporal position within the sequence, including;

means for iteratively comparing the desired temporal position to the indication of the duration stored for a current node of the tree representing the sequence wherein the current node and a located node are initially the root node;

means, operative when the duration stored for the current node is less than the desired temporal position, for subtracting the duration from the desired temporal position to obtain a new desired temporal position and selecting a next subnode of the located node and adjacent to the current node as the current node; and

means, operative when the duration stored for the current node is greater than the desired temporal position, for identifying the current node as the located node and for selecting any first subnode of the located node as the current node.

20. A digital information product defining a multimedia composition comprising a sequence of components, comprising:

a computer-readable medium; and

digital logic, stored on the computer-readable medium and defining a representation of the sequence using an indication of a tree having a plurality of leaves, wherein each leaf of the plurality of leaves of the tree represent components to be placed in the sequence and each having a duration, and wherein the tree relating the components has a plurality of nodes, each node having a plurality of subnodes, and wherein each node stores a value indicative of a total duration of all subnodes and leaves of the node, whereby a root node stores a value indicative of a total duration of the sequence.

21. A computer-implemented method locating a component at a desired temporal position within a sequence in a multimedia composition, wherein the sequence is defined by digital logic stored on a computer-readable medium and defining an indication of a tree having a plurality of leaves, wherein each leaf of the plurality of leaves of the tree represent components to be placed in the composition and each having a duration, and wherein the tree relating the components has a plurality of nodes, each node having a plurality of subnodes, and wherein each node stores a value indicative of a total duration of all subnodes and leaves of the node, whereby a root node stores a value indicative of a total duration of the sequence, the method comprising the steps of:

iteratively comparing the desired temporal position to the indication of the duration stored for a current node of the tree representing the sequence wherein the current node and a located node are initially the root node;

when the duration stored for the current node is less than the desired temporal position, subtracting the duration from the desired temporal position to obtain a new desired temporal position and selecting a next subnode of the located node and adjacent to the current node as the current node; and

when the duration stored for the current node is greater than the desired temporal position, identifying the current node as the located node and for selecting any first subnode of the located node as the current node.

22. An object-oriented system for representing a multimedia composition for implementation on a computer in an object-oriented framework, comprising:

(a) an abstract component class;

(b) a sequence class derived from the abstract component class and defining a first subclass of the component class, wherein a sequence object, an instance of the sequence class, comprises;

a collection of objects in the component class ordered using a search tree, wherein the search tree has a root node with a key indicative of the total duration of the sequence and nodes including subnodes of the root node and subnodes of other nodes, wherein each node has a key indicative of the total duration of any subnodes of the node and leaves, wherein the leaves of the search tree are the components in the sequence; and

a display method for displaying the collection of component objects continuously and sequentially; and

(c) a source clip class derived from the abstract component class and defining a second subclass of the abstract component class, wherein a source clip object, an instance of the source clip class, comprises;

an indication of a source of media data and a range within the source of media data; and

a display method for accessing the media data from the source according to the range and for displaying the media data.

7. The system of claim 23, further comprising means, operative when the virtual sample rate does not match the actual sample rate, for performing a rate conversion when the composition is played.

23. The object-oriented system of claim 22, wherein the sequence object further comprises an access method for identifying a component at a given temporal position in the sequence and including:

means for iteratively comparing the desired temporal position to the indication of the duration stored for a current node of the tree representing the sequence wherein the current node and a located node are initially the root node;

means, operative when the duration stored for the current node is less than the desired temporal position, for subtracting the duration from the desired temporal position to obtain a new desired temporal position and selecting a next subnode of the located node and adjacent to the current node as the current node; and

means, operative when the duration stored for the current node is greater than the desired temporal position, for identifying the current node as the located node and for selecting any first subnode of the located node as the current node.

24. The object-oriented system of claim 22, wherein the sequence object further comprises an creation method for creating the search tree, comprising:

means for determining a total duration for each group of sequentially adjacent components and iteratively determining total durations for groups of the groups; and

means for storing an indication of the sequence, including storing an indication of a search tree having leaves indicative of the components, nodes representing the groups of sequentially adjacent components and groups of groups, each node having a key defined by the total duration of group represented by the node and a root node representing the sequence and having a key defined by the total duration of the sequence.