Multimedia document using time box diagrams5717438Abstract A computer-implemented method of drawing a multimedia story including at least one episode is provided which represents a plurality of multimedia fries (e.g., text, sound, video, and picture files) graphically in a "time-box" which can be connected to other time boxes to for a time box diagram. A user can easily stretch or shrink, reposition, delete, or otherwise manipulate the fries graphically using the time boxes in order to produce a final multimedia story within given temporal (time) constraints. The method according to the invention includes steps of inputting to a processor story data having at least one episode, and, for each episode, generating first and second events and temporal constraints. Thereafter, from the temporal constraints, first coordinates of each of the first and second events for each of the episodes are determined, and the first and second events are assigned to layers based on a temporal position of the first and second events such that for each episode the first and second events are temporally connected. Thereafter, an order of events on each layer of the layers is permuted, and, from the order of the events on each layer and the temporal constraints, second coordinates of each of the first and second events for each of the episodes are determined. Finally, a layout of the story is generated. Claims Having thus described our invention, what we claim as new and desire to secure by Letters Patent is as follows: Description CROSS REFERENCE TO RELATED APPLICATIONS
TABLE 1
______________________________________
min opt max
______________________________________
sneeze 3.4 3.4 7.0
cough 5.0 6.8 9.0
______________________________________
A time interval I.sub.m can be viewed in terms of its two end-points, which will be called start(I.sub.m) and end(I.sub.m), where start(I.sub.m)<end(I.sub.m). The values of start(I.sub.m) and end(I.sub.m) are relative to the corresponding story S. A time interval I.sub.m is instantiated with respect to a story S when start(I.sub.m) and end(I.sub.m) are set relative to S. An example of the above multimedia story is discussed below. First, consider a multimedia story composed of the following set of objects with corresponding triples of lengths, as set forth below in Table 2.
TABLE 2
______________________________________
Type Min Opt Max
______________________________________
baloo text 3 3 15
pond video 7 10 14
delay delay 1 3 5
waltz sound 10 10 10
bear drawing 3 3 20
______________________________________
The following constraints in Table 3 are also present.
TABLE 3
______________________________________
costart (pond, delay)
meet (delay, baloo)
coend (pond, baloo)
meet (delay, bear)
meet (pond, waltz)
coend (waltz, bear)
______________________________________
The graphical user interface for the system allows operators to directly manipulate time boxes. Operators may simply drag and drop time boxes, resize them, connect them, separate them, and delete them. The interface to the system is menu-driven. For example, to relate "pond" and "waltz" by the relation meet, the operator touches ("clicks" upon) a time box to call up a menu, as shown in FIG. 3. When the operator selects the icon for meet, the menu disappears, and a time box with a question mark appears, as shown in FIG. 4. As the operator touches the "waltz" box, it replaces the question mark box, and the meet relationship is established between "pond" and "waltz". The time-box representation of the story "Baloo the bear" is shown in FIG. 5. Turning to solutions for stories, a solution for a story is an instantiation of all of its time intervals that satisfies the given constraints. Assuming that there exists a solution for it, the operator attempts to find the minimum amount of stretching or shrinking. That is, the operator attempts to find the distance between assigned interval lengths and the optimum values of those intervals. FIG. 6 illustrates an adjustment operation of the duration of a story. However, the method of finding the minimum amount of stretching/shrinking is known and is the subject of some of the above related applications incorporated herein by reference. Thus, for brevity, the method will not be repeated here. Turning now to the computation of time box diagrams, there are two basic approaches to computing time box diagrams. The first, which is referred to here as "static generation", involves computing the entire diagram at once (e.g., at the same time) and is discussed in detail below with reference to FIGS. 7-13J. The second, called "dynamic generation", computes the diagram incrementally by adding one time box (e.g., episode) at a time in an order unknown in advance and is discussed further in detail below with reference to FIGS. 14-16. Static generation is most appropriate for time box diagrams entirely created by the system, whereas dynamic generation is preferably in an interactive context in which the user creates the diagram one box at a time. Computing a time box diagram is a special case of the general problem of graph drawing. For the static generator according to the present invention, a story is first input, and thereafter the process proceeds in five phases (steps), as shown generally in FIG. 7. The first phase is a pre-processing phase 100, in which episodes are split into pairs of events (nodes). In the second phase (e.g., assigning X coordinates phase 200), X coordinates are found. In the third phase (e.g., a layering phase 300), the events are assigned to layers based on their location in time. The fourth phase (e.g., an ordering phase 400) permutes the events on each layer, thereby fixing the topology of the drawing. In the fifth phase (e.g., the assignment of Y coordinates phase 500), actual Y coordinates are computed for the episodes (e.g., time boxes). At the completion of the fifth phase, the layout of the story using time box representation is achieved. Looking at the phases of the process in greater detail, prior to the preprocessing phase 100 a story is input. The story includes a set of episodes {E.sub.i } with a length {l.sub.i } (play duration) and a set of temporal relations for {E.sub.i }. Further, .epsilon. is inputted which represents a minimum horizontal distance between time boxes and .delta. is inputted, which represents a minimum vertical distance between time boxes. Turning to the detailed processing flow, the first phase 100 is preprecessing after input of the story. The processing flow of the first phase is shown in FIG. 8. As shown in step 110 of FIG. 8, for each episode E.sub.i two events (nodes) are generated. That is, B(E.sub.i) (which means beginning of E.sub.i) and E(E.sub.i) (which means the ending of E.sub.i) are generated. Referring to FIGS. 9A-9B, the second phase 200 is described in greater detail. In the second phase 200, the assignment of the X coordinates (e.g., the coordinates along the horizontal or time axis) is performed. Specifically, linear programming or the like is used to determine precise X coordinates for the episodes. Referring to FIG. 9A, the process of assigning the X coordinates is shown. In step 210, for each episode E.sub.i, the length of the beginning and ending of the episode is represented by a linear constraint. More specifically, length l.sub.i of episode E.sub.i is equal to E(E.sub.i)-B(E.sub.i). R is given as the set of temporal relationships in step 220. In step 230, it is determined whether any temporal relationships r in set R remain to be considered. If YES, the flow proceeds to step 240 (shown in FIG. 9B) where it is determined what relationship r represents. Specifically, if r represents meet(E.sub.1, E.sub.2), then the flow proceeds to step 250 and the relationship is transformed into a constraint of B(E.sub.2)-E(E.sub.1).gtoreq..epsilon., wherein .epsilon. is the predetermined horizontal minimum distance between time boxes. Thereafter, the process loops back to step 230 to determine if there are any other temporal relationships r in set R to be considered. In step 240, if it is determined that r is cobegin(E.sub.1, E.sub.2), then the flow proceeds to step 260 and the relationship is transformed into a constraint of B(E.sub.1)=B(E.sub.2) and the process loops back to step 230 to determine if there are any other temporal relationships r in set R to be considered. In step 240, if it is determined that r is cooccur(E.sub.1, E.sub.2), then the flow proceeds to step 270 and the relationship is transformed into two linear constraints B(E.sub.1)=B(E.sub.2) and E(E.sub.1)=E(E.sub.2) and the process loops back to step 230 to determine if there are any other temporal relationships r in set R to be considered. Finally, in step 240, if it is determined that r is coend(E.sub.1, E.sub.2), then the flow proceeds to step 280 and the relationship is transformed into a linear constraint E(E.sub.1)=E(E.sub.2) and the process loops back to step 230 to determine if there are any other temporal relationships r in set R to be considered. When all temporal relationships r in set R have been considered (e.g., NO is determined in step 240), the processing flow continues to step 290 shown in FIG. 9C. In step 290, linear programming, such as the simplex method or the like, is used to minimize .SIGMA..sub.i E(E.sub.i) subject to the constraints generated in steps 250-280 and 210 above and thus to minimize event time. Thus, X coordinate values for B(E.sub.i), E(E.sub.i) for each episode are found. Referring to FIGS. 10A-10C, the third phase (layering) 300 assigns events (nodes) of episodes to layers based on their temporal location. In step 310, the values of the X coordinates of B(E.sub.i) and E(E.sub.i) for each episode are input. In step 320 of FIG. 10A, the events are sorted in increasing order with regard to the X coordinate values. In step 330, starting from the smallest X coordinate value to the largest, a layer is assigned thereto. Events having the same X coordinate (e.g., same horizontal position) are placed in the same layer. The result of the layering is given as: <L.sub.0, . . . , L.sub.k >. In step 340, for each episode, if B(E.sub.i) and E(E.sub.i) are not on consecutive layers, dummy events (e.g., d.sub.1 (E.sub.i), d.sub.2 (E.sub.i), . . . , d.sub.j (E.sub.i)) are inserted on the intermediate layers. Hence, for an edge from a node on layer i to a node on layer j, the algorithm creates dummy nodes on layers i+1, . . . , j-1. For each episode, a directed edge is inserted from B(E.sub.i) to d.sub.1 (E.sub.i), from d.sub.1 (E.sub.i) to D.sub.2 (E.sub.i), . . . , and from d.sub.j (E.sub.i to E(E.sub.i). Thus, the dummy events guarantee that edges only connect events (nodes) on consecutive layers. By the same token, if B(E.sub.i) and E(E.sub.i) are on consecutive layers, only one edge is inserted from B(E.sub.i) to E(E.sub.i). In step 360, for each meet(E.sub.i, E.sub.j) (e.g., E.sub.j immediately follows E.sub.i) if E(E.sub.i) and B(E.sub.i) are not on consecutive layers, dummy events d.sub.1 (E.sub.i, E.sub.j), d.sub.2 (E.sub.i, E.sub.j), . . . , and d.sub.k (E.sub.i, E.sub.j) are inserted on the intermediate layers. Thus, dummy events are used for filling in "blank" (empty) layers. In step 370, for each meet(E.sub.i, E.sub.j), edges are inserted from E(E.sub.i) to d.sub.1 (E.sub.i, E.sub.j), from d.sub.1 (E.sub.i, E.sub.j) to d.sub.2 (E.sub.i, E.sub.j), . . . , and from d.sub.k (E.sub.i, E.sub.j) to B(E.sub.j). If E(E.sub.i) and B(E.sub.j) are on consecutive layers, then only one edge is inserted from E(E.sub.i) to B(E.sub.j). Referring to FIG. 11, the fourth phase 400 of ordering (e.g., deciding the relative orders of events on each layer) is performed. Thus, the inventive process vertically orders the events (nodes) on each layer. Thus, the relative vertical orders of events on each layer is determined. As shown in FIG. 11, the ordering process is shown in greater detail. First, in step 410 the process orders the first layer (layer 0) arbitrarily. In step 420, for each of the remaining layers (1, . . . , n) from left to right, the events are sorted on that layer according to the median position of an event's (node's) neighbors on the previous level, and collisions are resolved arbitrarily. For example, in layer L.sub.k events A and B are present and in layer L.sub.k+1 events C and D are present. If there is an edge from A to C, from A to D, from B to C, and from B to D, the position of C is the median of position A and B, and likewise is D. This represents a "collision". In step 430, the relative order of each event on each layer, is obtained from steps 410 and 420. Thus, the ordering step determines the topology of the diagram, since edge crossings are completely determined by the ordering on each layer. In the fifth phase 500 and referring to FIG. 13A, the assignment of the Y coordinates (e.g., the coordinates along the vertical axis) is illustrated and is described hereinbelow. Generally, linear programming or the like is used to determine precise Y coordinates for the time boxes. Specifically, for each episode, the relationship y(B(Ei))=y(d.sub.1 (E.sub.i))=. . . ,=y(d.sub.j (E.sub.i))=y(E(E.sub.i) is set, as shown in step 510. d.sub.k (E.sub.i) represents the dummy events inserted between B(E.sub.i) and E(E.sub.i) inserted in step 340 above. Thus, step 510 makes sure that the Y coordinate is the same across a time box (episode) and relates to drawing the time box as a box. In step 520, for each meet(E.sub.i, E.sub.j), the relationship of y(d.sub.1 (B(E.sub.i, E.sub.j)))=y(d.sub.2 (B(E.sub.i, E.sub.j)))= . . . =y(d.sub.k (E.sub.i, E.sub.j))=y(B(E.sub.i, E.sub.j)) is set. d.sub.1 (E.sub.i, E.sub.i) represents the dummy events inserted in step 360 described above. Thus, step 520 makes sure that, for example in a meet relationship, episode E.sub.i (time box) may be easily connected to episode E.sub.j even with multiple intermediate layers (dummy) therebetween and the Y coordinate is different. Thus, as shown above, dummy events are useful for the time boxes and for the meet relationship. In step 530, for each layer, r.sub.1, . . . , r.sub.k is set as the relative ordering of events on a layer (as determined in step 400 above). Then, y(r.sub.2)-y(r.sub.1) is set greater than or equal to .delta.,y(r.sub.3)-y(r.sub.2) is set greater than or equal to .delta., . . . , and y(r.sub.k)-y(r.sub.k-1) is set greater than or equal to .delta., where .delta. is the predetermined minimum vertical distance between time boxes. In step 540, subject to the constraints from steps 510 to 530, linear programming is used with the objective function ›min.SIGMA. .vertline.y(e.sub.i)-y(e.sub.j).vertline.! for each pair of events, and e.sub.j, such that: {e.sub.i is either B(E.sub.k) or E(E.sub.k) and e.sub.j is either B(E.sub.1) or E(E.sub.1); and {meet (E.sub.k, E.sub.1) or cobegin (E.sub.k, E.sub.l) or coend (E.sub.k, E.sub.l) or coocur (E.sub.k, E.sub.l)} for some episodes E.sub.k and E.sub.l. Thus, at the conclusion of the Y coordinate assignment step, in step 550 the Y coordinate values for each event are found. Moreover, at the end of the fifth phase 500, all time boxes have been assigned X and Y coordinates and as shown the layout of the story using time box representation is achieved. An example and corresponding results at various steps of the process of the static generator processing flow of FIG. 7 is given below and in FIGS. 13A-13J. Obviously, this is simply one example of the process, as is known by one of ordinary skill in the art within the purview of this application. Further, it is noted that the example is not complete in that it does not show all the steps or their results. First, a story is input having five episodes E.sub.1, E.sub.2, E.sub.3, E.sub.4, and E.sub.5. Temporal relationships are established of cobegin(E.sub.1, E.sub.4), meet(E.sub.1, E.sub.2), meet(E.sub.2, E.sub.3), meet(E.sub.4, E.sub.5), and coend(E.sub.3, E.sub.5). .epsilon. is set to 3 and .delta. is set to 2. The length of the episodes in this example are l.sub.1 =3, l.sub.2 =4, l.sub.3 =5,l.sub.4 =7, and l.sub.5 =5. A set of events is generated as shown below. More specifically, the result of 110 is as follows: {B(E.sub.1), E(E.sub.1), B(E.sub.2), . . . , E(E.sub.5)} The results of each of steps 260-280 of the assigning of X coordinates (e.g., the coordinates along the horizontal axis) processing are shown in FIG. 13A. As mentioned previously, if in step 240, it was determined that r is cobegin(E.sub.1, E.sub.2), then step 260 is processed and the linear constraint B(E.sub.1 =B(E.sub.2) is generated. In step 270, if it was determined that r is cooccur(E.sub.1, E.sub.2), then the flow proceeds to step 270 and the linear constraints B(E.sub.1)=B(E.sub.2) and E(E.sub.1)=E(E.sub.2) are generated. Similarly, in step 280, if it was determined that r is coend(E.sub.1, E.sub.2) in step 240, then the linear constraint E(E.sub.1)=E(E.sub.2) is generated. The results of steps 210 and 250 based on the above example are shown in FIGS. 13B and 13C. As mentioned earlier, in step 210, for each episode E.sub.i, the length of the beginning and ending of the episode is found. More specifically, length l.sub.i of episode E.sub.i generates a linear constraint of E(E.sub.i)-B(E.sub.i).tbd.l.sub.i. For step 250, if r represents meet(E.sub.1, E.sub.2) as determined in step 240, then the linear constraint B(E.sub.2)-E(E.sub.1).gtoreq..epsilon. is generated. The objective function of step 290 of the above example is shown in FIG. 13D. The result of the assigning of the X coordinates of step 290 of phase 2 is shown in FIG. 13E. The leftmost position of FIG. 13E represents the origin (in terms of the X coordinate) or beginning of the episodes or story. In step 290, linear programming is used to minimize .SIGMA..sub.i E(E.sub.i) subject to the constraints generated in steps 250-280 and step 210 above. Thus, X coordinate values for B(E.sub.i), E(E.sub.i) for each episode are found, as shown in FIG. 13E. The result of the layering step 330 is shown in FIG. 13F. That is, in step 330, starting from the smallest X coordinate value to the largest, a layer is assigned thereto. Events having the same X coordinate (e.g., same horizontal position) are placed in the same layer. The result of the layering is given as shown. The results of the relative ordering of events in each layer (step 420) is illustrated in FIG. 13G. In step 420, for each of the remaining layers from left to right, the events are sorted on that layer according to the median position of an events's (node's) neighbors on the previous level, and collisions are resolved arbitrarily. As noted previously, in the layering step, dummy events (e.g., d.sub.1 (E.sub.4), d.sub.2 (E.sub.4) etc.) are inserted when the beginning and end of the time boxes (episodes) are on nonconsecutive layers and when the two events connected by the meet relationships of the episodes are not on consecutive layers. The results of steps 510 and 530 are shown in FIGS. 13H-13I, respectively. In the step 510, for each episode E.sub.i, the relationship y(B(E.sub.i)=y(E(E.sub.i) is set, as shown. In step 530, the result of relative ordering is shown. Specifically, in step 530, for each layer, r.sub.1, . . . , r.sub.k is set as the relative ordering of events on a layer (as determined in step 400 above). Then, y(r.sub.2)-y(r.sub.1) is set greater than or equal to .delta., y(r.sub.3)-y(r.sub.2) is set greater than or equal to .delta., . . . , and y(r.sub.k)-y(r.sub.k-1) is set greater than or equal to .delta., where .delta. is the predetermined minimum vertical distance between time boxes. FIG. 13J illustrates the objective function of step 540 in which subject to the constraints from steps 510 to 530, linear programming is used with the objective function for each pair of events. Turning to the dynamic generator of the invention and referring to FIG. 14, the processing steps 1100-1500 for the dynamic generator is shown. Inputted to the dynamic generator are the previous story and layout and the new story of which the new layout is to be computed according to the present invention. In drawing the time box diagram, with the invention the changes are reflected between the previous story and the new story, and the invention makes drawing the new story with the smallest amount of changes possible from the previous story. The steps used by the dynamic generator are the same as the static generator, with small changes being made in steps 1200, 1400 and 1500 (step 1100 is the same as step 100 for the static generator and step 1300 is the same as step 300 of the static generator). Thus, FIGS. 15-16 illustrate and hereinbelow are described only the changes in the steps 1200 1400, and 1500. In each step, if there is anything which can be reused from the calculation of the time box diagram of the previous story, it is used to compute the drawing of the new story in the dynamic generator. Step 1200 is the same as step 200 of the static generator discussed above (and as shown in FIGS. 9A-9C). The only change is reflected in step 2900 of the dynamic generator (which roughly corresponds to step of 290 of the static generator described above). Specifically, in step 2900, linear programming is used to minimize .SIGMA. .vertline.X.sub.new (ni)-X.sub.prev (ni).vertline., where n.sub.i is either B(E.sub.k) or E(E.sub.k) for some episode E.sub.k. X.sub.new represents the X coordinate of an event in the new story, whereas X.sub.prev represents the X coordinate of an event in the previous story. The objective function above makes sure that the horizontal position of the times boxes of the new story minimally change from the time box diagram of the previous story. In the ordering step 1400, as shown in FIG. 16, starting from layer 0 to the last layer, the following steps are performed. In step 1410, for each event, if it is in the previous story, it is given the relative order of it in the layer as in the previous story, i.e., according to the y coordinate in the previous story. In step 1420, if the event is not in the previous story, the event is placed at the median position of its in-neighbors. Regarding the step of the assignments of y coordinates (step 1500), this step is performed exactly the same as in the static generator step 500, which is detailed in steps 510-540. The only change is given to the objective function in step 540. In the dynamic generator, the new objective function is min (M .SIGMA. .vertline.y.sub.new (n.sub.i)-y.sub.prev (n.sub.i).vertline.+.SIGMA.(y.sub.new (e.sub.i)-y.sub.new (e.sub.j)), where n.sub.i is either B(E.sub.k) or E(E.sub.k) for some episode E.sub.k and e.sub.i is explained in step 530 above. y.sub.new represents the y coordinate in the new story, whereas y.sub.prev represents the y coordinate in the previous story, and M is any positive integer. If M is larger, then the amount of change is smaller. With the objective function above, it is made sure that the vertical position of the times boxes of the new story minimally change from the time box diagram of the previous story. Thus, the present invention provides a novel approach to representing multimedia documents. A key feature of the invention is focusing upon the temporal dimension of multimedia elements by expressing them as time boxes, and on the arrangement of these elements in terms of a system of temporal constraints. The present invention provides a unique and unobvious method of computation such time boxes in terms of both solving the system of constraints and of visualizing the system as a time box diagram. Moreover, the present invention uses the temporal relationships among multimedia objects to describe a multimedia document as a temporally constrained system. In the inventive model for a multimedia document, multimedia objects are the fundamental electronic building blocks. Just as ordinary building blocks can be stacked or placed next to each other, the inventive electronic building blocks can be constrained to start together, end together, occur one after the other, or coincide. The documents themselves have lengths in the temporal dimension and these lengths can be "stretched." Visually, the electronic building blocks are represented with "time boxes" and the time boxes have lengths corresponding to the lengths of the documents. The present invention represents the system of temporal constraints with time box diagrams. In these two-dimensional diagrams, the horizontal direction denotes time, and the vertical direction is used to show concurrency of blocks. The invention determines horizontal positions for the time boxes that conform to the temporal constraints and determines vertical positions so as to maximize the legibility and aesthetics of the diagram. Moreover, the present invention is directed to developing the time box model and the computation of time box diagrams. Thus, in contrast to the conventional systems which deal with time as a time line or a multiple time lines, the present invention allows a much easier method of composing and playing multimedia documents since temporal constraints are dealt with as relationships and not necessarily in absolute terms. While the invention has been described in terms of a single preferred embodiment, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.
|
Same subclass Same class Consider this |
||||||||||