Method and system for temporally formatting data presentation in time-dependent documents

• US 5,515,490 A
• Filed: 11/05/1993
• Issued: 05/07/1996
• Est. Priority Date: 11/05/1993
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Buchanan, M. Cecelia, Zellweger, Polle T.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Burwell, Joseph R.
• Application Number:
  US08/148,743
• Time in Patent Office: 914 Days
• Field of Search: 395/148, 395/149, 395/152, 395/153, 395/154, 395/161
• US Class Current: 715/209
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• 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/234318 by decomposing into objects, e.g. MPEG-4 objects
• CPC Class Codes: H04N 21/43072 of multiple content streams on the same device
• CPC Class Codes: H04N 21/44012 involving rendering scenes according to scene graphs, e.g. MPEG-4 scene graphs

Abstract

A method and system automatically produce a temporal layout for controlling the presentation of a multimedia document. A partial temporal layout, or schedule, is produced during a compiletime phase of the method from duration information about the media items included in the document, and from the temporal relationships between the media items, as specified by a document author. Several temporal relationships are supported, including "simultaneous with", for synchronization of two media items or events, and relationships such as "before by 10 seconds." The temporal formatter positions media data items having predictable behavior in time according to the specified temporal relationships and using the specified durations, and creates an auxiliary temporal layout with unresolved times for each media data item or event therein having unpredictable behavior. The temporal formatter automatically produces temporal layouts for documents that include media items for which internal events and continuously adjustable durations are specified, thereby providing for very flexible positioning of media items in time without the author'"'"'s involvement. The author of the document may specify a flexibility metric at the media or event level related to the continuously adjustable durations that provides the temporal formatter with guidance as to how to best position temporally related media items in time. In an illustrated embodiment, the flexibility metric consists of duration-adjustment costs, and the temporal formatter uses linear programming to solve for solutions to equations formulating the temporal constraints between connected components in the document.

Claims

1. A method of temporally formatting first and second temporally related media items included in a time-dependent document in an information presentation system;

the information presentation system including memory for storing data, a processor connected for accessing the data stored in the memory, and at least one media presentation device;

the data stored in the memory including instruction data indicating instructions the processor executes;

the method comprising;

operating the processor to obtain, for each of the first and second media items, at least one pair of temporally adjacent media item event data items, referred to as a pair of temporally adjacent events, identifying a media item segment;

each event in each pair of temporally adjacent events marking a point in time in the respective media item such that a second event in the pair of events follows a first event in time;

each media item segment indicating whether occurrence of the media item segment in the time-dependent document is predictable or unpredictable;

operating the processor to obtain temporal constraint data indicating a time ordering relation value specified between first and second temporally related event data items, referred to hereafter as a pair of temporally related events, identified from among the temporally adjacent events;

a first one of the temporally related events being an event included in a media item segment in the first media item and a second one of the temporally related events being an event included in a media item segment in the second media item;

operating the processor to obtain a durational time data item, hereafter referred to as a duration, for each respective media item segment;

each durational time data item indicating an elapsed time for presenting the respective media item segment on the at least one media presentation device;

each durational time data item further indicating whether the duration is predictable or unpredictable;

each predictable duration indicating a range of predictable elapsed presentation durations for a respective media item segment; and

for each respective media item segment having a predictable occurrence and a predictable media segment duration, operating the processor to assign a document presentation time value to each event included in the respective media item segment using the range of predictable elapsed presentation durations indicated for the respective media item segment and using the temporal constraint data specified between the respective media item segment and a second media item segment;

each respective media item segment for which document presentation time values are assigned having a computed presentation duration falling within the range of predictable elapsed durations for the respective media item segment;

the document presentation time values assigned satisfying the temporal constraint data specified between the respective media item segment and the second media item segment.

2. The temporal formatting method of claim 1 wherein

each respective media item segment indicates flexibility metric data measuring a presentation quality of the respective media item segment at each of selected durations within the range of predictable elapsed presentation durations when the media item segment is presented by the at least one media presentation device for the selected duration;

and

operating the processor to assign the document presentation time value to each event in each respective media item segment includes selecting a duration, referred to as a selected duration, within the range of predictable elapsed presentation durations using the flexibility metric data, and assigning the document presentation time values to the respective media item segment on the basis of the selected duration;

the selected duration being the duration in the range of durations that simultaneously produces document presentation time values that satisfy the temporal constraint data specified between the respective media item segment and a second media item segment and that provide an acceptable presentation quality when the respective media item segment is presented by the at least one media presentation device for the selected duration.

3. The temporal formatting method of claim 1

where in the range of predictable elapsed presentation durations for a respective media item segment further includes an optimum duration indicating a durational time value that produces a preferred presentation quality for the respective media item segment when the respective media item segment is presented by the at least one media presentation device for the optimum duration;

wherein each respective media item segment indicates flexibility metric data measuring a deviation from the preferred presentation quality of the respective media item segment at respective durations other than the optimum duration within the range of predictable elapsed presentation durations when the media item segment is presented by the at least one media presentation device for the respective duration; and

wherein, when document presentation time values cannot be assigned that are consistent with the optimum duration for the respective media item segment and still satisfy the temporal constraint data, the step of operating the processor to assign a document presentation time value to each event in each respective media item segment includes using the flexibility metric data to determine an adjusted predictable elapsed duration larger or smaller than the optimum duration, referred to as an adjusted duration, within the range of predictable elapsed presentation durations indicated by the respective media item segment;

the adjusted duration producing assigned document presentation time values satisfying the temporal constraint data specified between the respective media item segment and a second media item segment while producing a presentation quality that deviates by an acceptable amount from the preferred presentation quality of the respective media item segment, as measured by the flexibility metric data.

4. The temporal formatting method of claim 3 wherein

the flexibility metric data indicates a penalty value for adjusting the predictable elapsed presentation duration of a respective media item segment to an adjusted duration different from the optimum duration;

and

using the flexibility metric data to determine the adjusted predictable elapsed presentation duration for a respective media item segment includes shortening or lengthening the optimum duration such that the adjusted duration incurs a minimal penalty value.

5. The temporal formatting method of claim 4 wherein the penalty value indicated by the flexibility metric for each respective media item segment is a cost associated with shortening or lengthening the optimum duration of the respective media item segment, and

wherein the step of using the flexibility metric data to determine the adjusted predictable elapsed presentation duration includes optimizing an overall cost of lengthening and shortening media item segment durations for respective media item segments.

6. The temporal formatting method of claim 5 wherein optimizing the overall cost includes solving a function of at least three variables including a time at which each event should occur, a length of time an event occurs prior to its optimum time of occurrence, and a length of time an event occurs later than its optimum time of occurrence;

the values of the at least three variables being subject to a plurality of linear constraints selected from a group of constraints including media item segment durations, the cost associated with shortening or lengthening the optimum duration of a respective media item segment, and temporal constraint data.

7. The temporal formatting method of claim 1 wherein

each media item includes only one pair of temporally adjacent media item event data items identifying a media item segment such that the one pair of temporally adjacent events marks beginning and ending points in time respectively of the media item and defines a media item having coarse granularity;

the temporal constraint data indicates a time ordering relation value specified between a beginning or ending event of the first media item and a beginning or ending event of the second media item; and

assigning document presentation times assigns times to the beginning and ending events in each media item.

8. The temporal formatting method of claim 1 wherein each media item includes two or more pairs of temporally adjacent media item event data items identifying two or more media item segments defining a media item having fine granularity;

each media item segment being a portion of a media item.

9. The temporal formatting method of claim 1 wherein the media item segment is a dynamic media item segment producing a series of changing perceptions to a document reader during presentation of the dynamic media item segment in the time-dependent document;

the media segment duration of the dynamic media item segment being a cumulative duration of each of the series of changing perceptions.

10. The temporal formatting method of claim 1 wherein the media item segment is a static media item segment producing a single static, unchanging perception to a document reader during presentation of the static media item segment in the time-dependent document;

the media segment duration of the static media item segment being imposed on the static media item segment and indicating a durational time value for presenting the static media item segment during presentation of the time-dependent document.

11. The temporal formatting method of claim 1 wherein assigning document presentation times to events included in media item segments occurs prior to the runtime presentation of the time-dependent document to a user of the information presentation system.

12. The temporal formatting method of claim 11 further including

operating the processor to identify as having unpredictable behavior each respective media item segment indicating an unpredictable occurrence or an unpredictable media segment duration;

and

operating the processor to produce a second schedule data structure including a presentation command for each media item segment indicating unpredictable behavior;

the presentation command indicating an unresolved document presentation time assigned to a starting event in a media item segment having an unpredictable occurrence;

the presentation command further indicating an unresolved document presentation time assigned to an ending event in a media item segment having an unpredictable duration.

13. The temporal formatting method of claim 12 further including operating the processor to assign document presentation times to the unresolved document presentation times in the second schedule data structure at the time the time-dependent document is presented under the control of the first schedule data structure;

the first and second schedule data structures together controlling presentation of media items having predictable and unpredictable behavior in the time-dependent document.

14. The temporal formatting method of claim 1 further including operating the processor to produce a first schedule data structure for controlling presentation by the at least one media presentation device of each respective predictable media item segment having a predictable occurrence and a predictable duration;

the first schedule data structure including a presentation command indicating the document presentation time value for each media item event data item;

the first schedule data structure, when used to control presentation of the time-dependent document, causing a pair of temporally related media items to be presented at assigned document presentation times that satisfy the time ordering relation specified between them.

15. A method for use in a processor-controlled machine for temporally formatting a time-dependent document, hereafter referred to as a multimedia document, including a plurality of media items each capable of producing human perceptions when presented by a media presentation device;

the processor-controlled machine including memory for storing data, and a processor connected for accessing the data stored in the memory;

the data stored in the memory including instruction data indicating instructions the processor executes to control operation of the machine;

the method comprising;

obtaining from memory, for each media item included in the multimedia document, media item duration data, flexibility metric data, and temporal constraint data;

the media item duration data indicating a range of durational presentation time values, referred to as durations, for the respective media item;

the range of durations including an optimum duration;

the flexibility metric data indicating a measurement associated with each of selected durations other than the optimum duration within the range of durations;

the measurement indicating the temporal constraint data indicating a time ordering relation value specified between a respective media item and a second media item; and

assigning document presentation time values to media items using the media item duration data, the flexibility metric data, and the temporal constraint data;

each document presentation time value assigned to a respective one of the media items producing a computed duration within the range of durations indicated for the respective media item, and satisfying the temporal constraint data specified between the respective media item and a second media item;

the document presentation time values assigned to media items being computed by solving a function that optimizes a measurement associated with lengthening and shortening media item durations for respective media items;

the function being subject to a plurality of constraints selected from a group of constraints including media item durations, flexibility metric data for respective media item durations, and temporal constraint data between pairs of media items.

16. The temporal formatting method of claim 15 wherein the optimum duration specified for a respective media item indicates a durational time value that produces a preferred presentation quality for the respective media item when the respective media item is presented by a media presentation device for the optimum duration;

wherein the flexibility metric data associating a measurement with each of selected durations within the range of durations is cost data indicating a quality of presentation cost associated with deviating from the optimum duration by shortening or lengthening the optimum duration of a respective media item;

wherein the group of constraints to which the function is subject includes the cost data; and

wherein the function is solved to optimize an overall quality of presentation associated with shortening or lengthening the optimum duration of respective media items while still satisfying the temporal constraint data specified between pairs of media items.

17. The temporal formatting method of claim 16 further including

obtaining from memory, for each media item included in the multimedia document, a first data item indicating whether occurrence of the media item in the multimedia document is predictable or unpredictable, and a second data item indicating whether the media item duration is predictable or unpredictable;

and wherein

the step of assigning document presentation time values to media items includes identifying media items having predictable behavior, wherein predictable behavior is defined as having a predictable occurrence and a predictable duration, using the first and second data items; and

solving the function for media items having predictable behavior.

18. The temporal formatting method of claim 17 further including

identifying as having unpredictable behavior each respective media item segment indicating an unpredictable occurrence or an unpredictable media segment duration;

and

assigning an unresolved document presentation starting time to a media item having an unpredictable occurrence and assigning an unresolved document ending presentation time to media item having an unpredictable duration.

19. A method of temporally formatting a plurality of media items included in a time-dependent document in an information presentation system;

the information presentation system including memory for storing data, a processor connected for accessing the data stored in the memory, and a plurality of media presentation devices;

the data stored in the memory including instruction data indicating instructions the processor executes;

the method comprising;

operating the processor to obtain, for each media item, at least one pair of temporally adjacent media item event data items, referred to as a pair of temporally adjacent events, identifying a media item segment;

each event in a pair of temporally adjacent events marking a point in time in the respective media item segment such that a second event in the pair of events follows a first event in time with no intervening media item events specified between the pair of temporally adjacent events;

each media item segment indicating whether occurrence of the media item segment in the time-dependent document is predictable or unpredictable;

operating the processor to obtain a durational time data item, hereafter referred to as a duration, for each respective media item segment;

each durational time data item indicating an elapsed time for presentation of the media item segment by a respective one of the media presentation devices;

each durational time data item further indicating whether the duration is predictable or unpredictable;

each predictable duration including a range of predictable elapsed presentation durations including a minimum duration, an optimum duration, and a maximum duration for presenting the respective media item segment;

the optimum duration indicating a durational time value that produces a preferred presentation quality for the respective media item segment when the respective media item segment is presented by a respective one of the media presentation devices for the optimum duration;

each predictable duration further indicating flexibility metric data measuring a deviation from the preferred presentation quality of the respective media item segment at each respective duration within the range of durations when the media item segment is presented by the at least one media presentation device for the respective duration;

the flexibility metric data indicating a penalty value for adjusting the predictable elapsed presentation duration of a respective media item segment to an adjusted duration different from the optimum duration;

operating the processor to obtain temporal constraint data indicating a time ordering relation value specified between first and second temporally related event data items, referred to hereafter as a pair of temporally related events, identified from among the temporally adjacent events;

a first one of the temporally related events being an event included in a first media item segment and a second one of the temporally related events being an event included in a second media item segment;

operating the processor to identify media item segments indicating a predictable occurrence and a predictable media segment duration as having predictable behavior, and to identify media item segments indicating an unpredictable occurrence or an unpredictable media segment duration as having unpredictable behavior;

for each respective media item segment having predictable behavior, operating the processor to assign a document presentation time value to each event included in the respective media item segment;

each document presentation time value assigned producing a computed duration within the range of durations indicated for the respective media item segment, and satisfying the temporal constraint data specified between the respective media item segment and a second media item segment;

the computed duration being an adjusted duration when document presentation time values cannot be assigned that are consistent with the optimum duration for the respective media item segment and still satisfy the temporal constraint data;

the adjusted duration being determined using the flexibility metric data and producing assigned document presentation time values satisfying the temporal constraint data specified between the respective media item segment and a second media item segment while producing a presentation quality that deviates by an acceptable amount from the preferred presentation quality of the respective media item segment, as measured by an acceptably small penalty value indicated by the flexibility metric data; and

for each respective media item segment having unpredictable behavior, operating the processor to assign an unresolved document presentation time to a starting event in a media item segment having an unpredictable occurrence, and to assign an unresolved document presentation time assigned to an ending event in a media item segment having an unpredictable duration.

20. The temporal formatting method of claim 19 further including

operating the processor to produce a first schedule data structure for controlling presentation on the at least one media presentation device of each respective predictable media item segment having predictable behavior;

the first schedule data structure including a presentation command indicating the document presentation time value for each media item event data item;

the first schedule data structure, when used to control presentation of the time-dependent document, causing a pair of temporally related media items to be presented at assigned document presentation times that satisfy the time ordering relation specified between them;

operating the processor to produce a second schedule data structure including a presentation command for each media item segment indicating unpredictable behavior;

the presentation command indicating an unresolved document presentation time assigned to a starting event in a media item segment having an unpredictable occurrence;

the presentation command further indicating an unresolved document presentation time assigned to an ending event in a media item segment having an unpredictable duration; and

operating the processor to assign document presentation times to the unresolved document presentation times in the second schedule data structure at the time the time-dependent document is presented under the control of the first schedule data structure;

the first and second schedule data structures together controlling presentation of media items having predictable and unpredictable behavior in the time-dependent document.

21. The temporal formatting method of claim 19 wherein the penalty value indicated by the flexibility metric for each respective media item segment is a cost associated with shortening or lengthening the optimum duration of the respective media item segment, and

wherein the step of operating the processor to assign document presentation time values to events included in respective media item segments includes solving a function to optimize an overall cost of lengthening and shortening media item segment durations for respective media item segments.

22. The temporal formatting method of claim 19 wherein the time ordering relation specified between temporally related events specifies a time ordering relation between media item segments included in the same media item.

23. The temporal formatting method of claim 19 wherein the time ordering relation specified between temporally related events specifies a time ordering relation between media item segments included in different media items.

24. The temporal formatting method of claim 19 wherein the step of operating the processor to identify media item segments having predictable and unpredictable behavior includes

grouping media item event data items, referred to as events, included in media item segments into connected components of temporally related events using respective media item durations and temporal constraint data;

a first event being temporally related to a second event if a time ordering relation is specified between the first and second events or if the first and second event identify a media item segment having a media item duration;

a first connected component including events having no temporal relationship to events included in a second connected component; and

evaluating each connected component to determine whether the connected component has predictable or unpredictable behavior;

a connected component having unpredictable behavior when the connected component includes an unpredictable event or an event is included in a media item segment indicating an unpredictable duration;

a connected component having predictable behavior when the connected component includes only predictable events each included in a media item segment indicating a predictable duration.

25. The temporal formatting method of claim 24 wherein the step of operating the processor to assign document presentation times to events included in media item segments having predictable behavior includes positioning events in each connected component in relative temporal order within the connected component.

26. A method for use in a processor-controlled multimedia authoring system for temporally formatting a multimedia document including a plurality of media items each capable of producing human perceptions when presented by a media presentation device;

the multimedia authoring system including input circuitry connected to a user input device for producing user signals indicating actions of a system user;

memory for storing data;

at least one media presentation device; and

a processor connected for receiving the user signals from the input circuitry, for accessing the data stored in the memory, and for presenting signals indicating a media item to the media presentation device;

the data stored in the memory including instruction data indicating instructions the processor executes;

the method comprising;

receiving first user signals from the user input device indicating actions identifying media items to be included in a multimedia document;

in response to the first user signals, producing a media item data structure for each respective media item identified for inclusion in the multimedia document;

the media item data structure indicating starting and ending events in the media item;

receiving second user signals from the user input device indicating actions assigning durations and duration measurement data to each respective media item;

in response to the second user signals, modifying the media item data structure to further indicate a durational time data item, hereafter referred to as a duration, used by a media presentation device for presentation of the media item from the starting event to the ending event;

a duration indicating a range of elapsed presentation durations for a respective media item including an optimum duration;

a duration further indicating flexibility metric data associating duration measurement data at selected durations other than the optimum duration within the range of elapsed presentation durations when the media item is presented by a media presentation device for the selected duration;

receiving third user signals from the user input device indicating actions assigning temporal constraints to pairs of media items;

in response to the third user signals, producing and storing temporal constraint data indicating a time ordering relation value specified by the user between media items;

receiving fourth user signals from the user input device indicating a request to produce a main schedule for the media items included in the multimedia document; and

in response to the fourth user signals, assigning document presentation time values to events included in respective media items;

the document presentation time values assigned producing a computed duration for each media item that falls within the range of elapsed presentation durations for the respective media item while satisfying the temporal constraint data specified between a respective pair of media items;

the computed duration for a respective media item being an adjusted duration when the optimum duration specified for a respective media item would not produce document presentation time values that satisfy the temporal constraint data specified between a respective pair of media items;

the adjusted duration being determined by solving a function to optimize an overall measurement associated with lengthening and shortening media item durations for respective media items;

the function being subject to a plurality of constraints selected from a group of constraints including media item durations, the flexibility metric data associated with selected durations, and temporal constraint data.

27. The method for temporally formatting a multimedia document of claim 26 wherein the optimum duration specified for a respective media item indicates a durational time value that produces a preferred presentation quality for the respective media item when the respective media item is presented by a media presentation device for the optimum duration;

wherein the flexibility metric data associating a measurement with each of selected durations within the range of durations is cost data indicating a quality of presentation cost associated with deviating from the optimum duration by shortening or lengthening the optimum duration of a respective media item;

wherein the group of constraints to which the function is subject includes the cost data; and

wherein the function is solved to optimize an overall quality of presentation associated with shortening or lengthening the optimum duration of respective media items while still satisfying the temporal constraint data specified between pairs of media items.

28. The method for temporally formatting a multimedia document of claim 26 wherein the media item data structure further indicates whether occurrence of the media item in the time-dependent document is predictable or unpredictable, and whether the duration is predictable or unpredictable;

and wherein the method further includes

producing a main schedule including document presentation time values assigned for media items having predictable behavior;

producing an auxiliary schedule in addition to the main schedule;

the auxiliary schedule indicating an unresolved document presentation time for each media item having an unpredictable duration or an unpredictable occurrence;

receiving fifth user signals indicating a request from the user to present the multimedia document according to the main and auxiliary schedules, and

in response to the fifth user signals, presenting the media items included in the multimedia document on the media presentation device according to the document presentation time values assigned in the main and auxiliary schedules;

document presentation time values being assigned to the unresolved document presentation time values in the auxiliary schedule during runtime as the multimedia document is being presented.

29. The method for temporally formatting a multimedia document of claim 26 wherein

the first user signals from the user input device further indicate actions identifying media item segments included in the media items to be included in a multimedia document;

each media item segment is identified in the media item data structure for a respective media item by a pair of temporally adjacent media item event data items, referred to as a pair of temporally adjacent events;

each event in each pair of temporally adjacent events marking a point in time in the respective media item such that a second event in the pair of events follows a first event in time with no intervening events specified between the first and second events;

the third user signals from the user input device further indicates actions assigning temporal constraints to a pair of events included in a single media item or included in respective first and second media items;

a pair of events having a time ordering relation value specified therefor being referred to as a pair of temporally related events;

the user having the capability to specify a time ordering relation between events internal to the single media item or to the respective first and second media items; and

the step of assigning document presentation time values further includes assigning document presentation time values to the events included in media item segments;

the document presentation time values assigned producing a computed duration for each media item segment that falls within the range of elapsed presentation durations for the respective media item while satisfying the temporal constraint data specified between a respective pair of temporally related events;

the function optimizing an overall measurement associated with lengthening and shortening media item durations for respective media item segments.

30. A machine for temporally formatting a time-dependent document, hereafter referred to as a multimedia document, including a plurality of media items each capable of producing human perceptions when presented by a media presentation device;

the machine including memory for storing data, and

a processor connected for accessing the data stored in the memory;

the data stored in the memory including instruction data indicating instructions the processor executes;

the processor, in executing the instructions stored in the memory, obtaining from memory, for each media item included in the multimedia document, media item duration data and temporal constraint data;

the media item duration data indicating a range of durational presentation time values, referred to as durations, for the respective media item;

the range of durations including an optimum duration;

the media item duration data further indicating flexibility metric data associating a measurement with each of selected durations other than the optimum duration within the range of durations;

the temporal constraint data indicating a time ordering relation value specified between a respective media item and a second media item;

the processor, further in executing the instructions stored in the memory, assigning document presentation time values to media items;

each document presentation time value assigned to a respective one of the media items producing a computed duration within the range of durations indicated for the respective media item, and satisfying the temporal constraint data specified between the respective media item and a second media item;

the document presentation time values assigned to media items being computed by solving a function to optimize a measurement associated with lengthening and shortening media item durations for respective media items;

the function being subject to a plurality of constraints selected from a group of constraints including media item durations, flexibility metric data for respective media item durations, and temporal constraint data between pairs of media items.

31. The machine of claim 30 wherein the optimum duration specified for a respective media item indicates a durational time value that produces a preferred presentation quality for the respective media item when the respective media item is presented by a media presentation device for the optimum duration;

wherein the flexibility metric data associating a measurement with each of selected durations within the range of durations is cost data indicating a quality of presentation cost associated with deviating from the optimum duration by shortening or lengthening the optimum duration of a respective media item;

wherein the group of constraints to which the function is subject includes the cost data; and

wherein the function is solved to optimize an overall quality of presentation associated with shortening or lengthening the optimum duration of respective media items while still satisfying the temporal constraint data between pairs of media items.

32. A processor-controlled multimedia authoring system for producing, temporally formatting, and presenting a multimedia document including a plurality of media items;

the system including

input circuitry connected to a user input device for producing user signals indicating actions of a system user;

a media signal source for storing or receiving a plurality of sets of signals;

each set of signals indicating a media item capable of producing human perceptions when presented by a media presentation device;

first output circuitry connected to a first media presentation device having a display area for presenting images;

second output circuitry connected to a second media presentation device for receiving audio signals and presenting sound using the audio signals;

a processor connected for receiving the user signals from the input circuitry, connected for providing images to the first output circuitry, and connected for providing audio signals to the second output circuitry;

memory for storing data;

the data stored in the memory including instruction data indicating instructions the processor executes;

the processor being further connected for accessing the data stored in the memory;

the processor, in executing the instructions, receiving first user signals from the user input device indicating actions identifying media item segments of media items to be included in a multimedia document;

the processor, in executing the instructions in response to the first user signals, producing a media item data structure indicating data for a respective one of the media items included in the multimedia document;

the media item data structure indicating at least one pair of temporally adjacent media item event data items, referred to as a pair of temporally adjacent events, identifying a media item segment;

each event in each pair of temporally adjacent events marking a point in time in the respective media item such that a second event in the pair of events follows a first event in time;

the media item data structure further indicating whether occurrence of the media item segment in the time-dependent document is predictable or unpredictable;

the processor, further in executing the instructions, receiving second user signals from the user input device indicating actions assigning durations and measurement values to respective media item segments;

the processor, in executing the instructions in response to the second user signals, modifying the media item data structure indicating a respective media item segment to further indicate a durational time data item, hereafter referred to as a duration, used by a media presentation device for presentation of the media item segment;

the media item data structure further indicating whether the duration is predictable or unpredictable;

each predictable duration indicating a range of predictable elapsed presentation durations for a respective media item segment indicating a range of durations including an optimum duration;

the optimum duration indicating a durational time value that produces a preferred presentation quality for the respective media item segment when the respective media item segment is presented by a media presentation device for the optimum duration;

each predictable duration further indicating cost data measuring a cost of deviation from the preferred presentation quality of the respective media item segment at respective durations other than the optimum duration within the range of predictable elapsed presentation durations when the media item segment is presented by a media presentation device for the respective duration;

the processor, further in executing the instructions, receiving third user signals from the user input device indicating actions assigning temporal constraints to pairs of media item segments;

the processor, in executing the instructions in response to the third user signals, producing and storing temporal constraint data indicating a time ordering relation value specified by the user between events, identified from among the temporally adjacent events indicated by each media item data structure;

a pair of events having a time ordering relation value specified therefor being referred to as a pair of temporally related events;

the processor, further in executing the instructions, receiving fourth user signals from the user input device indicating a request to produce a main schedule for media items included in the multimedia document having predictable occurrences and predictable durations;

the processor, in executing the instructions in response to the fourth user signals, assigning document presentation time values to events included in respective media item segments;

the document presentation time values assigned satisfying the temporal constraint data specified between a respective pair of temporally related events while producing a presentation quality for a respective media item segment that deviates, when necessary, by an acceptable amount from the preferred presentation quality of the respective media item segment, as measured by the cost data;

the processor, further in executing the instructions for assigning document presentation time values, solving a function to optimize an overall cost of lengthening and shortening media item segment durations for respective media item segments;

the function being subject to a plurality of constraints that are selected from a group of constraints including media item segment durations, the cost data associated with deviating from the optimum duration by shortening or lengthening the optimum duration of a respective media item segment, and temporal constraint data.

33. The processor-controlled multimedia authoring system of claim 32 wherein

the processor, further in executing the instructions, produces an auxiliary schedule in addition to the main schedule;

the auxiliary schedule indicating an unresolved document presentation time for each media item segment having an unpredictable duration or an unpredictable occurrence; and

the processor, further in executing the instructions, in response to fifth user signals indicating a request from the user to present the multimedia document according to the main and auxiliary schedules, presents the multimedia document according to the document presentation time values assigned in the main and auxiliary schedules, using media items stored in the media signal source and presenting media items on the first and second media presentation devices;

the processor, in executing the instructions for presenting the multimedia document, assigning document presentation time values to the unresolved document presentation time values in the auxiliary schedule as the multimedia document is being presented.