Manufacturing video graphics

FIELD OF THE INVENTION

Embodiments of the present invention relate to motion synthesis. In particular, they relate to automated synthetic motion that include multiple interacting objects.

BACKGROUND TO THE INVENTION

Video graphics may include scenes of battlefields, panic crowds, team sports etc that require a huge amount of stylized, dense interactions between multiple characters. Generating such scenes in video graphics is important for a variety of applications including, for example, television programs, advertisements, video games and movies.

These scenes may be created by either manually composing singly captured or key- framed motions or simultaneously capturing the motions of multiple persons by a motion capture system.

Manually composing the scene using singly captured motions or key-framed motions requires a huge amount of labor. Simultaneously capturing the motions of multiple persons has a number of drawbacks, it requires the recording of large amounts of data, obscuration of one character by another during motion capture can result in incomplete data and the complexity of processing real life interactions.

it would be desirable to use better automated techniques to manufacture video graphics

It would also be desirable to adaptively control the interaction of a robot, such as for example a humanoid or anthropomorphic robot, with another object particularly if that another object dynamically varies.

BRIEF DESCRIPTION OF VARIOUS EMBODIMENTS OF THE INVENTION According to various, but not necessarily all, embodiments of the invention there is provided an apparatus comprising: a memory system storing a plurality of sequences, each sequence comprising data for reproducing a different pattern of interactions between a respective plurality of moving characters and storing a combination data structure defining for each sequence connectability of that sequence with other ones of the plurality of sequences; a processor configured to determine pair-wise combinations of the stored sequences, by selecting sequences for pair-wise combination that are defined as connectable by the stored combination data structure, wherein each pair-wise combination has in common at least one of their respective plurality of moving characters and configured to use determined pair- wise combinations of the stored sequences to produce and output video graphics comprising a series of sequences in which movable characters repetitively interact in different combinations.

According to various, but not necessarily all, embodiments of the invention there is provided a method of manufacturing video graphics comprising: storing a plurality of sequences, each sequence comprising data for reproducing a different pattern of interactions between a respective plurality of moving characters; storing a combination data structure defining for each sequence connectability of that sequence with other ones of the plurality of sequences; determining pair-wise combinations of the stored sequences, by selecting sequences for pair-wise combination that are defined as connectable by the stored combination data structure, wherein each pair-wise combination has in common at least one of their respective plurality of moving characters; and using the determined pair-wise combinations of the stored sequences to produce video graphics comprising a series of sequences in which movable characters repetitively interact in different combinations.

According to various, but not necessarily all, embodiments of the invention there is provided an apparatus for manufacturing a pre-cursor product used in the manufacturing of video graphics comprising: a memory; a user interface configure to enable user specification of a pattern of action units for two or more moving characters; and a processor configured to generate candidate video sequences where each candidate video sequence reproduces a user-specified pattern of action units for the two or more moving characters and configured to select at least one candidate sequence from the candidate sequences and store the selected candidate sequence in the memory.

According to various, but not necessarily all, embodiments of the invention there is provided a method for manufacturing a pre-cursor product used in the manufacturing of video graphics comprising: enabling user specification of a pattern of action units for two or more moving characters; generating putative candidate video sequences where each putative candidate video sequence reproduces the specified patterns of action units for the two or more moving characters; performing data processing to select at least one candidate sequence from the putative candidate sequences; and storing the selected candidate sequence.

According to various, but not necessarily all, embodiments of the invention there is provided a method comprising: creating building blocks at an action level; creating building blocks at a video graphic level that correspond to the building blocks at the action level; storing a data structure recording allowed combinations of building blocks; and combining building blocks at the video graphics level using the data structure

The apparatus may be for example a data processing system such as a computer.

According to various, but not necessarily all, embodiments of the invention there is provided an apparatus comprising: a memory system storing a plurality of sequences, each sequence comprising data for reproducing a different pattern of dynamic interactions between a respective plurality of objects and storing a combination data structure defining for each sequence connectability of that sequence with other ones of the plurality of sequences; a processor configured to determine pair-wise combinations of the stored sequences, by selecting sequences for pair-wise combination that are defined as connectable by the stored combination data structure, wherein each pair-wise combination has in common at least one of their respective plurality of objects and configured to use determined pair-wise combinations of the stored sequences to produce output defining a series of sequences in which objects repetitively interact..

According to various, but not necessarily all, embodiments of the invention there is provided a method comprising: storing a plurality of sequences, each sequence comprising data for reproducing a different pattern of interactions between a respective plurality of objects; storing a combination data structure defining for each sequence connectability of that sequence with other ones of the plurality of sequences; determining pair-wise combinations of the stored sequences, by selecting sequences for pair-wise combination that are defined as connectable by the stored combination data structure, wherein each pair-wise combination has in common at least one of their respective plurality of objects; and using the determined pair-wise combinations of the stored sequences to produce output defining a series of sequences in which objects repetitively interact.

According to various, but not necessarily all, embodiments of the invention there is provided an apparatus comprising: a memory; a user interface configured to enable user specification of a pattern of action units for two or more objects; and a processor configured to generate candidate sequences where each candidate sequence defines a user-specified pattern of action units for the two or more objects and configured to select at least one candidate sequence from the candidate sequences and store the selected candidate sequence in the memory.

According to various, but not necessarily all, embodiments of the invention there is provided a method comprising: enabling user specification of a pattern of action units for two or more objects; generating putative candidate sequences where each putative candidate sequence reproduces the specified patterns of action units for the two or more objects; performing data processing to select at least one candidate sequence from the putative candidate sequences; and storing the selected candidate sequence.

Objects may, for example, be representations of physical things such as, for example, a robot and objects the robot interacts with or they may be representations of virtual things such as, for example, animated characters. BRIEF DESCRIPTION OF THE DRAWINGS

For a better understanding of various examples of embodiments of the present invention reference will now be made by way of example only to the accompanying drawings in which:

Fig 1 schematically illustrates a method of manufacturing video graphics; Fig 2A schematically illustrates an apparatus configured to manufacture pre-cursor products used in the manufacture of video graphics;

Fig 2B schematically illustrates an apparatus configured to use the pre-cursor products to manufacture video graphics;

Fig 3 schematically illustrates an example of an action-level motion graph used to represent action units and the order in which they can occur;

Fig 4 schematically illustrates a method by which a user-specified action sequence is converted to a video sequence; Figs 5A and 5B schematically illustrate temporal combination of video sequences; Figs 6A and 6B schematically illustrate spatial combination of video sequences; and Fig 7 schematically illustrates a method of automatically composing video graphics by combining video sequences,

DETAILED DESCRIPTION OF VARIOUS EMBODIMENTS OF THE INVENTION

The examples described below use a 'bottom up' approach to motion synthesis. The examples generate output defining dynamically varying interactions between different multiple objects. Building blocks are created and then subsequently intelligently combined to create an output where multiple objects interact. The building blocks may be preformed sequences that define different patterns of interactions between objects.

At run-time, output can be either automatically or interactively generated where objects closely interact with one another by combining the building blocks.

One approach is: illustrated in Fig 1. The method comprises:

(1 ) capturing the motion of a single object;

(2) creating building blocks at a higher topographical level (3) creating building blocks at a lower physical level

(4) generating in a connectivity data structure that records allowed combinations of building blocks at the physical level

(5) generating an output automatically by combining the building blocks at the lower physical level.

The steps (1 ) to (4) may be performed in a pre-processing stage whereas the step (5) may be performed in a run-time stage.

Objects may, for example, be representations of physical things such as, for example, a robot and an object or objects the robot interacts with or they may be representations of virtual things such as, for example, animated characters. A robot may be a humanoid or anthropomorphic robot that, for example, manipulates another object or objects.

The embodiments described in detail below are described in relation to an embodiment in which video graphics are manufactured rather than control commands for a robot. However, it will be readily understood by the person skilled in the art how to reapply the teaching for controlling robots.

The examples described below use a 'bottom up' approach to generating scenes involving dynamically varying interactions between different multiple characters. User defined building blocks are created and then subsequently intelligently combined to create a scene where multiple characters interact with each other in different combinations in a stylized manner. A user is a person involved in generating scenes involving dynamically varying interactions between different multiple characters rather than a person who views the generated scenes.

The user defined building blocks are preformed video sequences that define different patterns of interactions between characters. The building block may, for example, follow the interaction rule of "background character: action ^" , "main character: reaction", "main character: action ^" and "background character: eliminated".

At run-time, the user can either automatically or interactively generate scenes where a large number of characters closely interact with one another by combining the building blocks.

One approach is illustrated in Fig 1 . The method 1 comprises:

(1 ) capturing the motion of a single character, in block 2

(2) creating building blocks (action sequences) at the action level in block 4

(3) creating building blocks (video sequences) at the video graphics level in block 8

(4) generating in block 8 a connectivity data structure that records allowed combinations of building blocks (video sequences) at the video graphics level (5) composing in block 10 a video graphics scene automatically by combining the building blocks (video sequences) at the video graphics level.

The block 2, 4, 6 and 8 may be performed in a pre-processing stage 12 whereas the block 10 may be performed in a run-time stage 14.

The pre-processing stage 12 and the run-time stage 14 may be performed in the same or different apparatuses such as the apparatus 6 illustrated in Fig 2.

The apparatus 6A illustrated in Fig 2A is configured to perform the pre-processing stage 12. The inputs to the pre-processing stage 12, the captured motion 1 1 and a plurality of action sequences 9, are stored in memory 2. The data processor 5 is controlled by computer program 7 A to process the motion data 1 1 and the action sequences 9 to produce as outputs the video sequences 4 and the connectivity data structure 3. The video sequences 4 and the connectivity data structure 3 are, in this example, stored in memory 2 but it other examples they may be output from the apparatus 6A. A user interface 13 is provided to enable user control of the processor 5.

The apparatus 6B illustrated in Fig 2B is configured to perform the run-time stage 14. The inputs to the run-time stage 14, the plurality of video sequences 4 and the connectivity data structure 2, are stored in memory 2. The data processor 5 is controlled by computer program 7B to use the connectivity data structure 2 to combine the video sequences 4 to produce video graphics output 8, which in this example is stored in memory 2. A user interface 13 is provided to enable user control of the processor 5.

Similar reference numerals are used to designate similar functional components in Figs 2A and 2B and to emphasise that the pre-processing stage 12 and the run-time stage 14 may be performed by the same or different apparatuses.

The processor 5 is configured to read from and write to the memory 2. The processor 5 may also comprise an output interface via which data and/or commands are output by the processor and an input interface via which data and/or commands are input to the processor 5.

The memory 2 stores a computer program 7A, 7B comprising computer program instructions that control the operation of the apparatus 6A, 6B when loaded into the processor 5. The computer program instructions 7A, 7B provide the logic and routines that enable the apparatus to perform the methods illustrated in Figs. The processor 5 by reading the memory 2 is able to load and execute the computer program 7A, 7B.

The computer program may arrive at the apparatus via any suitable delivery mechanism. The delivery mechanism may be, for example, a computer-readable storage medium, a computer program product, a memory device, a record medium such as a CD-ROM or DVD, an article of manufacture that tangibly embodies the computer program. The delivery mechanism may be a signal configured to reliably transfer the computer program.

Although the memory 2 is illustrated as a single component it may be implemented as one or more separate components some or all of which may be integrated/removable and/or may provide permanent/semi-permanent/ dynamic/cached storage.

Referring back to Fig 1 , at block 2, motion data 1 1 for a single character is obtained. The motion data 1 1 is preferably obtained using motion capture (Mocap).

In motion capture, movement of one actor is sampled many times per second. The sampled data is mapped to a 3D model so that the model performs the same actions as the actor. The movement of the model is recorded as video graphics i.e. a series of static images (frames).

At block 4, building blocks (action sequences 9) are created at the action level.

The movement of the model can be segmented into action units that occur in certain orders, e.g. by classifying movements based on the trajectories of the limbs. For some actions such as punching, falling and avoiding, the appropriate distance, orientation and timing for the actions to be launched are computed based on the trajectories of body segments and saved.

An action-level motion graph 20, similar to the one illustrated in Fig 3, may be used to represent the action units and the order in which they can occur.

The particular example of an action-level motion graph 20 illustrated in Fig 2 comprises a first standard pose 22 and a second standard pose 32.

Any one of the following actions can be launched from the first standard pose 22 before returning to the first standard pose 22: walk 23, low kick 24, avoid 25.

The following action can be launched from the first standard pose 22 to move to the second standard pose 32: dodge 26.

Any one of the following actions can be launched from the second standard pose 32 before returning to the second standard pose 32: punch 27, high kick 28.

The following action can be launched from the second standard pose 32 to move to the first standard pose 22: punch 29.

The action-level motion graph 20 is a state machine for the character. It defines the states (standard poses) and the allowable transitions from state to state. The action- level motion graph 20 defines the semantic action units 22-28 and a grammar for combining the action units in sequences. Each action unit is associated with recorded video graphics representing movement of the model for that action unit. The semantic action units 22-28 can be combined in sequences defined by the action-level motion graph 20 to represent movement of the model.

The user may specify building blocks (action sequences) 9 that define patterns of interactions between two characters by using the action units of the action-level motion graph. A pattern of interactions is typically a small number of action units (less than 10) in sequence where each action unit is assigned to a character and obeys the grammar of the action-level motion graph.

The building block (action sequence) 9 may, for example, follow ihe rule of "background character: action", "main character: reaction", "main character: action" and ^" background character: eliminated".

In the action level motion graph 20 illustrated in Fig 3, the sequence of action units of the main character, reaction and action, may, for example, be represented as the sequence of action units avoid 25, kick 24 or dodge 26, punch 27 or dodge 26 or kick 28.

At block 6, building blocks (video sequences) 4 are created at the video graphics level.

A user-specified action sequence 9 is converted to a video sequence 4, for example, using the method 40 illustrated in Fig 4.

The method 40 comprises: at block 42 input of an action sequence 9; at blocks 50, 52 using the action-level motion graphs 20 to generate putative candidate video sequences 4; and at block 56 evaluating the putative candidate video sequences 4 to select and store a video sequence 4.

At block 42, a user-specified action sequence 9 is provided. The action sequence is defined here as a Patternϋst, that describes the pattern of the interaction between two characters.

PatternUst ={( Char! ¹ DI , Annotation] ),...,( CharlDn,Annotationn)} ,

where Annotation! is an action unit 45 embedded in the action-level motion graph, ChariDi 46 is the identity of the character who performs this action, which is either 1 or 2, and n is the total number of actions in the pattern, typically less than 10.

in the Fig, the PatternList 44 has an ordered list of entries and the order defines an action pattern. Each entry specifies an action unit 45 and a character 48 for performing the action unit 45.

it should be noted that the list 44 oniy defines a starting order of the actions, and does not mean each character has to waif for the other character to finish its action in order to start a new action.

The use of a user specified action sequence enables short stylized interactions between the characters to be defined.

The initial conditions 48 of the characters are mainly determined based on the nature of the interactions. For fights, tackles, falling down and avoidance, the apparatus 8A roughly determines the location and orientation of the characters so that the initial actions become effective. Then, if collects samples by uniformly adjusting parameters such as distance, relative orientation of characters and timing of launching the initial actions around the initially set values.

The initial condition 48 may include, for example, distance between the two characters (r), the relative orientation of each character with respect to the other character (θ and θ ). and the delay in either of the character to start the first action.

The action sequence 9 is composed of the initial condition 48 of the two characters and the list 44 of actions performed by each of the characters.

At blocks 50, 52 a search is performed for putative video sequences 4 that are equivalent to the user specified action sequence 9. At block 50, the system lets the characters traverse the action-level motion graph 20 so that they follow the pattern of annotation given by the PatternList 44. The traversal of the first character Ch 1 is illustrated in the action-level motion graph 2O ₁ . The traversal of the second character Ch2 is illustrated in the action-level motion graph 2O ₂ .

It will be appreciated that there are multiple choices for the same action pattern. For example, the action-level motion graph 2d has two 'avoid' action units and the action-level motion graph 2O ₂ has two 'avoid' action units.

Since there are multiple choices for the same action pattern, all putative video sequences corresponding to the action pattern are generated. This corresponds to expanding a search tree from the action-level motion graph and identifying the action sequences within the search tree that correspond to the action pattern specified by the user.

Since the process of constructing the putative video sequences 4 involves the search tree expansion, the computational cost is in exponential order. In general, when fully expanding the search tree for evaluating the interactions of characters,

D the computational cost is A ,where A is the average number of available actions, and D is the depth of the tree to be expanded. However, this cost is greatly reduced by using short user-defined action patterns 44. As the patterns of actions are given, the number of actions n to be expanded at each level is few. This is because only short action patterns are defined. Longer interactions are generated by temporal concatenation of video sequences 4. Interactions involving more than two characters may be generated by spatially combining video sequences 4.

At block 58, the putative video sequences 4 obtained are evaluated and those with high scores are saved in memory 2 as video sequences 4 for the user specified action sequence 9. This process is repeated for multiple different user specified action sequences 9 to obtain and store multiple respective video sequences 4 in a database for reproducing the different action sequences 9.

The evaluation of the putative video sequences 4 may use a constraint function which may include one or more hard constraints and/or one or more soft constraints.

A hard constraint is a constraint that has to be strictly satisfied. A soft constraint provides a higher score the better the video sequence conforms to the constraint.

Typically, ail the putative video sequences 4 are filtered using the hard constraints, and then the fitness of the remaining video sequences is calculated using the soft constraints. The highest scoring putative video sequences 4 are stored in the memory 2 as video sequences 4.

Although the scheme to evaluate 58 the interactions is problem specific, a number of constraints are general enough to be applied for most interactions:

Hard Constraints: a) Order of actions: because the duration of each action is different, sometimes the overall order of the actions does not coincide with the pattern specified in the action sequence 42 such series of actions are discarded; and/or b) Penetrations: avoid video sequences that result in serious body penetration or overlap. Since the torso is the largest part of a human body, whenever a torso penetration is detected, the video sequence may be discarded.

Soft Constraints:

Any combination of the following constraints can evaluate a wide variety of video sequences:

a) Contacts: For some actions such as holding the hand, punching the face, and tackling the body of the other person, some parts of the bodies must contact either for a moment or throughout the timeline of the video sequence 4. Better scores are given to the series of actions which result in keeping such body parts closer. b) Keeping distance / relative orientation: For actions such as dancing, the characters need to stay close and face each other for some period. Similarly, for interactions such as one character punching and the other avoiding, the defender should get away from the punch, but needs to face the attacker while avoiding it. For these interactions, there are desired distances and relative orientations of some parts of the body at some moment / throughout the motion. We can evaluate the interactions based on the difference of the resulting values and the desired values.

c) Timing: For some combinations of actions such as attacking and defending, the actions performed by both characters need to be well synchronized. We consider the interactions with small timing differences to be better.

At block 8 a data structure 3, such as a connectivity table, is generated that records allowed combinations of building blocks at the video graphics level i.e. allowed combinations of video sequences 4.

The connectivity data structure 3 defines for each video sequence 4, the connectability of that video sequence with other video sequences 4 in pair-wise combinations to form video graphics. The connectability may indicate temporal connectability and/or spatial connectability.

The connectivity data structure 3 may also record in association with each video sequence the action sequence 44 from which it was generated.

Each video sequence 4 has start parameters that describe an initial condition 48 at the beginning of the video sequence and end parameters that describe a final condition at the end of the video sequence

The initial condition may include initial orientation and initial posture of the characters and an initial distance between characters.

The final condition may include final orientation and final posture of the characters and a final distance between characters, Referring to Figs 5A and 5B, temporal connectability from a leading video sequence

4A to a following video sequence 4B occurs when the start parameters of the following video sequence 4B and the end parameters of the leading video sequence 4A are within tolerance values that provide for continuity of video graphics when the leading and following video sequences are concatenated.

Temporal connectability is tested for every permutation and combination of pairs of video sequences 4 and the results recorded in the connectivity table.

Two video sequences 4A and 4B can be temporally concatenated if both of the characters A(1 ) and A{2) in a leading video sequence 4A start interacting again as the characters B(1 ) and B(2) in the following video sequence 4B (Fig 5A) or one of the characters A(1 ) or A(2) from the leading video sequence 4A joins the following video sequence 4B and starts to interact with a different character B(1 ) or B(2) and also the character in video sequence 4A who is not in video sequence 4B does not collide with the character in video sequence B who is not in video sequence 4A.

This may be expressed logically as:

TEMPORAL CONCATENATION[A, B]= MATCH[A(I ) ₅ B(I )] AND MATCH[A(2), B(2)] OR

MATCH[A(I ) ₅ B(2)] AND MATCH[A(2), B(I )] OR

MATCH[A(I ) ₅ B(I )] AND NOT MATCH[A(2), B(2)] AND NOT C0LLISI0N[A(2), B(2)] OR

MATCH[A(I ) ₅ B(2)] AND NOT MATCH[A(2) ₅ B(I )] AND NOT C0LLISI0N[A(2), B(1 )] OR

MATCH[A(2), B(I )] AND NOT MATCH[A(I ), B(2)] AND NOT COLUSION[A(I ) ₅ B(2)] OR

MATCH[A(2) ₅ B(2)] AND NOT MATCH[A(I ) ₅ B(I )] AND NOT COLLISION[A(I ), B(I )],

where TEMPORAL CONCATENATION[A, B] is TRUE is video sequence B can be concatenated to video sequence A, MATCH[X,Y] is TRUE if the motion represented by X and Y are continuous in the action motion graph, NOT MATCH[X, Y] is TRUE if the motion represented by X and Y are not continuous in the action motion graph and NOT COLLISION[X,Y] is TRUE if the character conducting X does not collide with the character conducting Y.

Spatial connectability is tested for every permutation and combination of pairs of video sequences 4 and the results recorded in the connectivity data structure 3.

The user might need a scene where more than two characters interact; we can compose such a scene by spatially combining video sequences 4 of two characters, for example, as illustrated in Figs 6A and 8B.

There are two conditions for such a combination. The common character in the two video sequences 4A, 4B must conduct the same series of actions for a continuous duration. The duration of overlap does not have to cover the whole video sequence. This condition is satisfied if, as illustrated in Fig 6A, the ending action unit(s) of one video sequence 4A and the initial action unit(s) of another video sequence 4B overlap or if, as illustrated in Fig 6B, the whole series of action units in a shorter video sequence 4B completely overlaps with the same series of action units in a longer video sequence 4A (Fig 6B),

This may be expressed logically as:

SPATIAL COMBINATION[A, B]=

IF( END ACTION[A(I )] = START ACTION[B(I )], TRUE) AND NOT C0LLISI0N[A(2), B(2)]

OR IF( END ACTION[A(2)] = START ACTION[B(I )], TRUE) AND NOT COLLISION[A(I ), B(2)]

OR

IF( END ACTION[A(I)] = START ACTI0N[B(2)], TRUE) AND NOT C0LLISI0N[A(2),B(1)]

OR

IF(END ACTI0N[A(2)] = START ACTI0N[B(2)], TRUE) AND NOT COLLISION[A(I ), B(I )]

OR

SUBSET [B. A] AND NOT COLLISION[A, B]

where SPATIAL COMBINATION^, B] is TRUE if video sequence B can be spatially combined with video sequence A, END ACTION[X] is the last action unit(s) for the character and video sequence represented by X and START ACTION[Y] is the first action unit(s) for the character and video sequence represented by X and SUBSET[X, Y] is TRUE if the video sequence X is wholly contained within video sequence Y. NOT COLLISION[A, B] means that the characters which are not common to video sequence A and B should not collide.

At block 10, a scene is automatically composed by combining the building blocks (video sequences) 4 at the video graphics level and is output as video graphics output 8 for storage in memory 2 or for rendering (not illustrated). An example of a suitable method 60 is illustrated in Fig 7.

The method 60 comprises: at block 62, the method 60 determines a set of video sequences 4 in the connectivity table which are connectable as a pair-wise combination to a target video sequence 4 and as such, after connection, have in common at least one character who moves with continuity in both the target video sequence 4 and the connectable video sequences 4. The target video sequence may be a current video sequence i.e. the method 60 may occur in real-time at run time.

At block 62, the method 60 selects, using evaluation criteria, a video sequence 4 for combination with the current video sequence from the set of video sequences 4.

The user can control the process by giving high-level commands that control the evaluation criteria.

The apparatus 6B excludes those video sequences in the set of video sequences that result in collisions. In case a video sequence 4 requires the apparatus 6B to add a new character to the scene, it is checked that the newly added character does not collide with any other characters present in the scene.

The system then selects the best video sequence, according to the evaluation criteria from the remaining video sequences of the set of video sequences.

The factor(s) taken into account to evaluate the set of video sequences may include one or more of the following:

a) Density of characters: Because there are going to be a large number of characters involved in the interactions, video sequences that allocate characters in the open space are favored.

This is evaluated as follows:

1 _ sd(p) = φ +1

where dp is the current density of characters at the region where the candidate video sequence p will occupy if it is concatenated.

b) Frequency of the usage: It is preferable to avoid repetition of similar movements, and lower scores are given to video sequences which have been recently used. We define a parameter Ip to represent the usage of the video sequence p; once a video sequence is used, its corresponding fp value is increased by one. On the other hand, the value is decreased by 10% each time other video sequences 4 are selected. The usage score of the video sequence is calculated as follows:

sf (P) = (1 -min( fpΛ ))

c) User preference: A simple interface is provided to the user to select the preferred type of action units that may be represented in action patterns 44. The video sequences that include such type of action units are given better scores: su(p) = 1 if the action satisfies the user's preference and su(ρ) = 0 if it does not.

The final score of a video sequence 4 is defined as the weighted sum of different factors such as the above factors:

S (p) = W ₀ S ₁ Ip) +WfS _f (p) + WuSjp) Equation (1 )

where p is the video sequence 4 to be evaluated. w _d , w _f , w _u are the weights for each factor, which we set as w _d ~ ϊ θ _h w _f ~ 1000 and w _u ~ 10000. The video sequence 4 in the set that returns the highest score is selected.

At block 88, the selected video sequence is combined with the target video sequence The combination may be a temporal combination or a spatial combination. The target video sequence is then updated, if necessary, and the method moves to block 82 again to repeat.

Thus the successively determined pair-wise combinations of the stored video sequences 4 are used to produce video graphics scenes 8 comprising a series of sequences in which movable characters repetitively interact in different combinations. The video graphics scenes 8 are stored as video graphics output 8 in the memory 2.

The thus manufactured video graphics output 8 may then be tangibly embodied on a machine readable physical medium 15 for distribution and use in a number of applications including, for example, television, advertisements, video games and movies. it may be arranged thai by default, of the two characters that interact in a video sequence one character appears from background while the other character moves, with continuity, from a preceding video sequence.

It may be arranged that both of the two characters that interact in a video sequence move, with continuity, from the same preceding video sequence.

It may be arranged that both of the two characters that interact in a video sequence appears move, with continuity, from different preceding video sequences.

it may be arranged that by default, of the two characters that were interacting in a current video sequence one character disappears to background when the current video sequence ends while the other character moves, with continuity, to a following video sequence.

It may be arranged that both of the two characters that interact in a current video sequence move, with continuity, to the following video sequence.

Thus when multiple characters continuously interact, they need to repeatedly enter and exit video sequences. For instance, if we want to design such a scene for two characters, both characters going out from the current video sequence need to rejoin in a following video sequence. However, sometimes such video sequences cannot be found due to the distinct initial conditions of the characters required for the following video sequence.

We solve this problem by giving the characters the degrees of freedom to adjust their locations, orientations and postures.

A locomotion planner is used to move a character that does not have the correct initial conditions to the character's nearest standard pose and then from that standard pose to the initial conditions required for the following video sequence.

We define a distance function that evaluates the difference between the current pose (Pc) and each standard pose (Ps) as follows: F[PcPs) = ( r,, - r _s ) ^* +( θ ,. ¹ - θ _s ¹ ) ^* +( θ , ² - Qc ) Equation (2) where re is the distance between the characters, θ _c and θ _c ^" are the angles between the line connecting the two characters and the direction each character facing, r _s , θ- ₌ ¹ , θ _s ^f are the corresponding values in the Standard pose.

The distance between the current status of the characters and each standard pose is calculated and the one with the smallest distance is selected: a/pm/πP F(Pe.P/) (3)

where Pj is the y ^' -th Standard pose, and Pc is the current status of the two characters.

As a result, even if a video sequence 4 cannot be immediately launched, one or more characters can be made to move around and adjust their poses to enable that video sequence to start. As for timing, if one character arrives to the corresponding posture in the Standard pose slightly earlier than the other character, we let the character wait there so that it is synchronized with its opponent before launching the next interaction video sequence.

Although, the pre-processing stage 12 of Fig 1 illustrates one method of providing suitable inputs to block 10, it should be appreciated that other methods may be used to provide those inputs. For example, a user could design the video sequences 4 herself or the video sequences 4 could be made from captured motion data of two persons or those which are manually designed by animators.

Although the number of characters in each video sequence described above (before spatial concatenation) has been two video sequences with more characters can be generated by expanding the game tree for all of the characters and then combining as explained above However, more computational time will be needed to expand the search tree.

The blocks illustrated in the Figs may represent steps in a method and/or sections of code in the computer program. The illustration of a particular order to the blocks does not necessarily imply that there is a required or preferred order for the blocks and the order and arrangement of the block may be varied. Furthermore, it may be possible for some steps to be omitted.

Although embodiments of the present invention have been described in the preceding paragraphs with reference to various examples, it should be appreciated that modifications to the examples given can be made without departing from the scope of the invention as claimed.

Features described in the preceding description may be used in combinations other than the combinations explicitly described.

Although functions have been described with reference to certain features, those functions may be performable by other features whether described or not.

Although features have been described with reference to certain embodiments, those features may also be present in other embodiments whether described or not.

Whilst endeavoring in the foregoing specification to draw attention to those features of the invention believed to be of particular importance it should be understood that the Applicant claims protection in respect of any patentable feature or combination of features hereinbefore referred to and/or shown in the drawings whether or not particular emphasis has been placed thereon.

I/we claim: