Systems and methods for creating and distributing modifiable animated video messages

CROSS-REFERENCE TO RELATED APPLICATIONS

0001The present application is a continuation of U.S. application Ser. No. 13/787,541 filed Mar. 6, 2013, which claims priority to U.S. Application No. 61/749,193 filed Jan. 4, 2013 and U.S. Application No. 61/607,377 filed Mar. 6, 2012. The aforementioned application(s) are hereby incorporated by reference in their entirety.

FIELD OF THE INVENTION

0002The present invention relates generally to computer generated graphics and more specifically to generating virtual character animations.

BACKGROUND

0003The generation of 3D content and in particular of 3D animated content is becoming increasingly popular. Despite this trend, creating 3D characters that can be animated is still typically left to artists with specialized training.

0004A 3D character is typically composed using one or more meshes, a skeleton and skinning weights. A mesh is typically a set of polygons defining the surface of an object, which often serves as the appearance of a 3D character. An object can be a character or any other discrete element in 3D visualization. A skeleton is typically a set of rigid items, or “bones”, generally under the mesh of an object, analogous to anatomical bones. These skeleton bones are typically bonded to the mesh in order to provide motion to the 3D character model. Rigging is the process of creating a suitable skeleton for a character, binding the skeleton to the character mesh using skinning weights and defining forward kinematic parameters or inverse kinematic parameters that determine how the character moves. The animation of a rigged 3D character involves applying motion data to the character's skeleton to drive the character's mesh. The generation of animations can be technically challenging and is often performed by artists with specialized training.

0005Patterns within computer generated 3D content can be found utilizing Principal Components Analysis (PCA). PCA is a process that utilizes an orthogonal transformation to convert a dataset of values into a set of values of linearly uncorrelated variables called principal components. A set of values expressed in terms of the principal components can be referred to as a feature vector. A feature vector can correspond to a particular aspect of 3D generated content such as a representation of a particular pattern or to the values of the pixels of an image.

SUMMARY OF THE INVENTION

0006Systems and methods in accordance with embodiments of the invention enable collaborative creation, transmission, sharing, non-linear exploration, and modification of animated video messages. One embodiment includes a video camera, a processor, a network interface, and storage containing an animated message application, and a 3D character model. In addition, the animated message application configures the processor to: capture a sequence of video frames using the video camera; detect a human face within a sequence of video frames; track changes in human facial expression of a human face detected within a sequence of video frames; map tracked changes in human facial expression to motion data, where the motion data is generated to animate the 3D character model; apply motion data to animate the 3D character model; render an animation of the 3D character model into a file as encoded video; and transmit the encoded video to a remote device via the network interface.

0007In a further embodiment, the 3D character model includes data describing: an articulated skeleton; at least one mesh; and skinning weights that determine the manner in which motion of the articulated skeleton deforms the at least one mesh.

0008In another embodiment, an articulated skeleton includes a plurality of bones configured to rotate in one or more degrees of freedom around joints, and a mesh is a plurality of vertices defining a surface comprising a plurality of polygons.

0009In a still further embodiment, the animation messaging application configures the processor to detect a human face within a sequence of video frames using a cascade of classifiers.

0010In still another embodiment, the storage contains a description of a space of human faces and facial expressions obtained using a training data set containing multiple images of human faces registered to a template image of a human face and multiple images of human facial expressions registered to the same template image of a human face, and the animation messaging application configures the processor to track changes in human facial expression of a human face detected within a sequence of video frames by configuring the processor to match the detected image of a human face to a point in the space of human faces and facial expressions using the description of a space of human faces and facial expressions.

0011In a yet further embodiment, the description of a space of human faces and facial expression is obtained by performing Principal Component Analysis (PCA) of a training data set containing multiple images of human faces registered to a template image of a human face and by performing PCA of multiple images of human facial expressions registered to the same template image of a human face to define a vector space of human faces and human facial expressions.

0012In yet another embodiment, the animation messaging application configures the processor to match a detected image of a human face to a point in the space of human faces and facial expressions using the description of a space of human faces and facial expressions by locating a vector within the space of human faces and human facial expressions that synthesizes an image of a human that is the closest match to the detected image of a human face in accordance with at least one matching criterion.

0013In a further embodiment again, the storage also contains a set of mappings from the space of human faces and facial expressions to a plurality of facial expressions for the 3D character model, where the plurality of facial expressions each represent a deformation of the mesh of the 3D character model, and the animation messaging application configures the processor to map tracked changes in human facial expression to motion data by configuring the processor to select a sequence of facial expressions for the 3D character based upon points in the space of human faces and facial expressions matching a detected image of a human face in a captured sequence of video frames and the set of mappings from the space of human faces and facial expressions to the plurality of facial expressions for the 3D character model.

0014In another embodiment again, the animation messaging application configures the processor to apply motion data to animate the 3D character model by configuring the processor to deform the mesh of the 3D character using a sequence of facial expressions for the 3D character model.

0015In a further additional embodiment, the animation messaging system further configures the processor to: detect an animation trigger; and animate the 3D character using additional motion data in response to the animation trigger.

0016In another additional embodiment, the animation messaging system further configures the processor to: detect an animation trigger; and animate object that shares a scene with the 3D character in response to the detection of an animation trigger.

0017In a still yet further embodiment, the animation messaging application further configures the processor to: receive a link from the remote location that identifies a location form which the encoded video can be retrieved; and send a message with the link to a second remote device.

0018In still yet another embodiment, the animation messaging application further configures the processor to: receive an interactive animated message comprising encoded video divided into a plurality of video sequences; select a video sequence from the plurality of video sequences; combine the selected video sequence with an additional video sequence to create a combined video sequence; and transmit the combined video sequence to a remote device via the network interface.

0019In a still further embodiment again, the animation messaging application further configures the processor to: receive an interactive animated message comprising encoded video divided into a plurality of video sequences; select at least one video sequence from the plurality of video sequences; and playback the selected at least one video sequence via a display device.

0020In still another embodiment again, a single device comprises the video camera, and processor.

0021A still further additional embodiment includes a video camera, a processor, a network interface, and storage containing an animated message application. In addition, the animated message application configures the processor to: capture a sequence of video frames using the video camera; detect a human face within a sequence of video frames; track changes in human facial expression of a human face detected within a sequence of video frames; map tracked changes in human facial expression to motion data, where the motion data is generated to animate the 3D character model; and transmit the motion data to a remote device via a network interface.

0022Still another additional embodiment also includes transmitting data identifying a 3D character model.

0023In a yet further embodiment again, the animation messaging application further configures the processor to: receive encoded video from the remote device via the network interface; detect an animation trigger; send additional motion data to the remote device via the network interface in response to the animation trigger; and receive updated encoded video from the remote device.

0024In yet another embodiment again, the animation messaging application further configures the processor to: receive encoded video from the remote device via the network interface; detect an animation trigger; send a message indicating the receipt of the animation trigger to the remote computing device; and receive updated encoded video from the remote device.

0025In a yet further additional embodiment, the animation messaging application further configures the processor to: receive an animated video message including motion data from a remote device, where the motion data comprises a plurality of animation sequences; select an animation sequence from the plurality of animation sequences; combine the motion data from the selected animation sequence with additional motion data to create combined motion data; and transmit the combined motion data to a remote device via a network interface.

0026In yet another additional embodiment, the animation messaging application further configures the processor to: receive an animated video message including motion data from a remote device, where the motion data comprises a plurality of animation sequences; select at least one animation sequence from the plurality of animation sequences; and render video using the selected at least one animation sequence.

0027In a further additional embodiment again, a single device comprises the video camera, and processor.

0028Another further embodiment includes a processor, a network interface, and storage containing an animated message application, and a 3D character model. In addition, the animated message application configures the processor to: receive a sequence of video frames from a remote device via a network interface; detect a human face within a sequence of video frames; track changes in human facial expression of a human face detected within a sequence of video frames; map tracked changes in human facial expression to motion data, where the motion data is generated to animate the 3D character model; apply motion data to animate the 3D character model; and render an animation of 3D character model into a file as encoded video.

0029In still another further embodiment, the animated message application configures the processor to transmit the encoded video to a remote device via a network interface.

0030Yet another further embodiment also includes a display; and a video decoder. In addition, the animated message application configures the processor to display the encoded video via the display and using the video decoder.

0031In another further embodiment again, the animated message application configures the processor to receive the 3D character model from a remote device via the network interface and store the 3D character in the storage.

0032In another further additional embodiment, the 3D character model is one of a plurality of 3D character models and the animated message application configures the processor to receive a selection of a 3D character model from the plurality of 3D character models from a remote device via the network interface, and is configured to apply the motion data to animate the selected 3D character model.

BRIEF DESCRIPTION OF THE DRAWINGS

0033<figref idref="DRAWINGS">FIG. 1</figref> illustrates a system for generating animated video messages in accordance with an embodiment of the invention.

0034<figref idref="DRAWINGS">FIG. 2</figref> is a flow chart illustrating a process for sending animated video messages in accordance with an embodiment of the invention.

0035<figref idref="DRAWINGS">FIG. 3</figref> is a flow chart illustrating a process of generating animated video messages in accordance with an embodiment of the invention.

0036<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart illustrating a process for detecting changes in human facial expressions in accordance with an embodiment of the invention.

0037<figref idref="DRAWINGS">FIG. 5</figref> is a flow chart illustrating a process for tracking changes across human facial expressions in accordance with an embodiment of the invention.

0038<figref idref="DRAWINGS">FIG. 6</figref> is a flow chart illustrating a process for generating character facial animation utilizing a mapped feature vector in accordance with an embodiment of the invention.

0039<figref idref="DRAWINGS">FIG. 7</figref> is a flow chart illustrating the application of animations to an animated video message from an animation trigger in accordance with an embodiment of the invention.

0040<figref idref="DRAWINGS">FIG. 8A</figref> is a screen shot illustrating a pose of a surprised human facial expression mirrored by a frame of character facial animation in accordance with an embodiment of the invention.

0041<figref idref="DRAWINGS">FIG. 8B</figref> is a screen shot illustrating a pose of an angry human facial expression mirrored by a frame of character facial animation in accordance with an embodiment of the invention.

0042<figref idref="DRAWINGS">FIG. 8C</figref> is a screen shot illustrating a pose of a neutral human facial expression mirrored by a frame of character facial animation in accordance with an embodiment of the invention.

0043<figref idref="DRAWINGS">FIG. 9</figref> conceptually illustrates an interactive animated video message in accordance with an embodiment of the invention. The story develops in a non-linear way where it could take different paths depending on the user interaction. The different options (e.g. Intro1A, Intro 1B, etc.) can be pre-generated or can be created interactively by the user.

0044<figref idref="DRAWINGS">FIG. 10</figref> conceptually illustrates the distribution of animated video messages and the reuse of animation sequences and/or video clips included within the distributed animated video messages to create additional animated video messages in accordance with embodiments of the invention. The distribution of the resulting animated video messages can involve end users, creators and users who have modified the story of the animated video message.

DETAILED DESCRIPTION

0045Turning now to the drawings, systems and methods for creating, and distributing modifiable animated video messages in accordance with embodiments of the invention are illustrated. In many embodiments, animated video messages can be generated by tracking human facial expressions in captured video images and using the tracked expressions to drive animation of a facial model of a character. The animated facial model can then be used to render video for display. In this way, animated video messages can be created using video captured by a camera integrated within or connected to a first networked computing device and displayed on a second networked computing device. In a number of embodiments, additional animations can be applied to a character in accordance with one or more animation triggers.

0046In many embodiments, video rendered using an animated facial model is played back with an audio accompaniment recorded during the capture of the video used to animate the facial model. In certain embodiments, video rendered using an animated facial model of a character can be translucently overlaid in real time on the video of the human face used to drive the animation so that the composite video images of the human face and the animated character generate an effect similar to that of an animated mask or makeup overlaid on the human face.

0047In many embodiments, human facial expressions can be tracked by defining a space that encompasses the variability in human faces and facial expressions. In a number of embodiments, methods for dimensionality reduction such as (but not limited to) Principal Component Analysis (PCA), Independent Component Analysis, Canonical Correlation Analysis, and Fisher's Linear Discriminant can be utilized to describe the space of human faces and facial expressions. When a PCA space of human facial expressions is defined using a training data set, techniques including (but not limited to) a cascade of classifiers can be utilized to identify and extract a human face from a video image. A facial expression can be tracked by obtaining the feature vector of the human face and its expression within the PCA space of human facial expressions. The feature vector within the PCA space of human faces and facial expressions that is the closest match to the human face and facial expression can then be mapped to a facial model of a character. In a number of embodiments, the character includes a 2D or a 3D facial model and a PCA space of the 2D or 3D character's facial expression is defined. Therefore, a set of mappings can be defined that enable the mapping of feature vectors from the PCA space of human faces and facial expressions to the PCA space of the 2D or 3D character's facial expression. In this way, a sequence of images of a human face can be used to extract a sequence of feature vectors that are mapped to the PCA space of the 3D character's facial expression. This sequence of mappings animates the 2D or 3D facial model of the character and the animated facial model can be used to render video. Techniques for animating a facial model of a character using images of human facial expressions are discussed further in U.S. Provisional Application No. 61/674,292 filed Jul. 20, 2012, titled “SYSTEMS AND METHODS FOR ANIMATING THE FACES OF 3D CHARACTERS USING IMAGES OF HUMAN FACES”, the disclosure of which is incorporated herein by reference in its entirety.

0048In many embodiments, the process of generating an animated message includes selecting a character from a library of multiple characters. In addition, a user can also select backdrops, props, text, and audio that can accompany the animation. Furthermore, a user can select camera movement, angle, orientation, zoom, and/or any other of a variety of parameters associated with rendering video from a 3D model of a scene. In several embodiments, the process of creating an animated message can be collaborative. One or more selections made by a first user can be changed by a second user to modify the rendered video. In addition, the second user can add additional animations, props, audio, text, and/or any other form of content to modify an animated message created by a first user.

0049In several embodiments, animated video messages can include additional animations applied to a character within an animated video message in accordance with an animation trigger. In certain embodiments, the detection of an animation trigger applies an additional animation using a technique including (but not limited to) concatenating the additional animation to an existing character animation, layering additional motion data indicative of the additional animation on top of existing motion data, and/or generating an animation that is associated with a character (such as but not limited to a sparking halo that appears on top of a character's head). The animation trigger can be any interaction with a networked computing device that can be detected and used to trigger the application of an additional animation to a character. Such triggers can include (but are not limited to) the detection of predetermined facial expressions or gestures using a camera, the detection of predetermined motions and/or interactions with the networked computing device using a motion sensor such as (but not limited to) an accelerometer, the detection of contact or touches using a touch screen, and/or the detection of predetermined sounds using a microphone. Particular animation triggers can cause predetermined animations to be applied to a character, such as (but not limited) applying a tickling animation to a character in response to detection of a predetermined sequence of touches via a touch screen, and/or applying a shaking animation to a character in response to detection of a shaking motion using an accelerometer. Techniques for blending multiple animations for application to 3D characters are discussed further in U.S. patent application Ser. No. 13/097,031 filed Aug. 28, 2011, titled “REAL-TIME AUTOMATIC CONCATENATION OF 3D ANIMATION SEQUENCES”, the disclosure of which is incorporated herein by reference in its entirety.

0050In various embodiments, animated video messages can be distributed over a network as content stored on servers accessible via a URL. In certain embodiments, animated video messages are distributed using the Wireless Application Protocol (WAP) for store-and-forward services such as the Multimedia Messaging Service (MMS) on networked computing devices.

0051In many embodiments, various processes that are utilized in the generation of an animated video message are performed by devices distributed across a network. These devices can include networked computing device that can include a video camera (such as but not limited to a personal computer, tablet computer, or a mobile phone), and/or network connected servers. These devices can perform any of a variety of functions related to the generation of an animated video message, such as (but not limited to) tracking changes in human facial expressions from captured video images, detecting animation triggers, generating character animations from the tracked human facial expressions and/or detected triggers, rendering character animations, displaying rendered character animations, and encoding the rendered character animations in a video. In addition, the devices can enable the collaborative creation of animated messages by permitting a first user to create an initial animated message that can be modified by a second device to produce a second animated message. Devices can be utilized for the performance of a specific function or generally utilized for a variety of functions related to the generation of animated video messages, such as (but not limited to) processing data from captured video images or displaying rendered character animations. Each device can perform all or only some of the functions related to the generation of animated video messages.

0052In a number of embodiments, the process of creating animated video messages is collaborative. In a number of embodiments the animated video message is created through a linear or a non-linear story where the animated video story blocks are pieced together by different users. The users can either choose pre-existing animated story blocks or they can create new ones. Animated video messages can be distributed between different users and animation sequences, and/or video clips within an animated video message can be further reused, augmented or expanded to create additional animated video messages. In this way, various animation sequences can be seeded into the social graph and can become building blocks for the creation of an increasing array of content. In a number of embodiments, the animated video messages that are distributed are interactive and users can determine the order in which animation sequences and/or video clips are played back. The additional content contained within interactive animated video messages (irrespective of whether used in playback of an animated video message by a specific user) can also be reused to create additional animated video messages. In one embodiment of the invention some story blocks of the animated video are pre-set and some others can be defined or customized by the user. Systems and methods for generating animated video messages, distributing animated video messages, interacting with animated video messages and reusing, or expanding animation sequences and/or video clips contained within animated video messages to create additional animated video messages in accordance with embodiments of the invention are discussed further below.

Systems for Generating Animated Video Messages

0053A processor configured via an appropriate software application can generate animated video messages using video images captured by a video camera and/or any of a variety of other sources of input including (but not limited to) sensors, touch screens, and/or microphones. Processors resident upon a networked computing device or a server connected to a network can perform a variety of functions related to generation of animated video messages, including (but not limited) to detecting changes in human facial expressions, detecting animation triggers, generating character facial animations from detected changes in human facial expressions, applying character animations upon recognizing an animation trigger and rendering character animations. Processors resident upon a networked computing device or server can also format data for transmission in a variety of formats, including the Wireless Application Protocol (WAP) for store-and-forward services such as the Multimedia Messaging Service (MMS) on networked computing devices or as content stored on servers accessible over a network via a URL.

0054In various embodiments, networked computing devices can send animated video messages to other networked computing devices over a network. These animated video messages can be generated by a networked computing device and sent to another networked computing device directly. Animated video messages can be sent directly utilizing any method, including (but not limited to) by streaming a rendered character facial animation to another networked computing device, sending tracked human facial expression data that enables a networked computing device to generate, render and display a character facial animation, or by sending character facial animation data to a networked computing device that enables a networked computing device to render and display a character facial animation. In certain embodiments, animated video messages include animations applied to a character according to recognition of an animation trigger and a networked computing device can generate motion data in response to the trigger locally and/or provide the animation trigger or a description of an animation to a networked computing device to generate appropriate motion data. Streaming can be accomplished by sending individual component packets of data from a rendered animated video message in a specific order where the packets of data are buffered by the networked computing device that receives the stream and plays back the animated video message in real time. Animated video messages can also be sent indirectly utilizing any method, including (but not limited to) generating, rendered, and/or storing a character animation, including character facial animation, on a server accessible to a networked computing device.

0055A system for generating animated video messages in accordance with an embodiment of the invention is illustrated in <figref idref="DRAWINGS">FIG. 1</figref>. Image capture devices <b>102</b> capable of capturing video images that include a human face can be connected or integrated with a networked computing device <b>104</b>. Each networked computing device <b>104</b> can be connected via a network <b>106</b>, such as (but not limited to) the Internet, to one or more servers <b>108</b> that can facilitate communication amongst networked computing devices or provide services related to generating animated video messages. Thereby, recipient networked computing devices <b>104</b> can receive animated video messages generated from the video images captured by the image capture device <b>102</b> over the network <b>106</b>.

0056In many embodiments, the generation of an animated video message can take place on the networked computing device <b>104</b> that captured the video of a human face or across various devices, such as across a combination of networked computing devices <b>104</b> and servers <b>108</b>. In certain embodiments, a networked computing device <b>104</b> can receive a selection of a 3D character via a user interface, capture video images using an image capture device <b>102</b> such as (but not limited to) a video camera, detect the changes in human facial expressions in the captured video images, recognize an animation trigger, generate character animation from tracking the changes in the human facial expressions or from applying motion data to a character based upon the recognition of an animation trigger, receive instructions concerning backdrops, text, audio, camera movement, angle, orientation, and/or zoom, render the character animation and send the rendered character animation to another networked computing device <b>104</b> over the network <b>106</b>. In several embodiments, a server <b>108</b> can render the character animation from a character animation generated on a networked computing device <b>104</b>. In many embodiments, a server <b>108</b> can generate and render character animation from changes detected in human facial expressions captured by a video camera or from motion data applied to a 3D character in accordance with a recognized animation trigger using a networked computing device. In a number of embodiments, a server <b>108</b> can detect changes in human facial expressions from video captured by a networked computing device <b>104</b>, generate a character animation and/or render video from the character animation. In several embodiments, a first networked computing device captures video images, a server detects changes in human facial expressions from captured video images, and a second networked computing device generates animation using the changes in human facial expression detected by the server and/or from animation applied to a 3D character in accordance with a recognized animation trigger and renders the animation for display. In particular embodiments, a first networked computing device captures video of human facial expression and/or detects one or more animation triggers. A second networked computing device can receive the captured video, detect changes in human facial expressions or recognize an animation trigger, generate a character facial animation from the tracked changes or other character animation in accordance with the animation trigger, and/or render the character animation. In a number of embodiments, the second networked computing device can change a variety of aspects of the animation including (but not limited) modifying the 3D character selection, modifying backdrops, props, text, audio, camera movement, angle, orientation, zoom, and/or any other characteristic of the animation that was controllable during the initial generation of the animation. In several embodiments, the networked computing device that creates or modifies an animation can control the extent to which collaborators can control aspects of the animation. Although specific distributions of processes across various devices are discussed above, as can be readily appreciated various processes involved in the generation of animated video messages can be performed by any of a variety of networked computing devices and servers during the distribution of animated video messages in accordance with embodiments of the invention.

0057Although specific systems for generating and distributing animated video messages are discussed above, animated video messages can be transmitted over a variety of systems using a variety of techniques as appropriate to the requirements of specific applications in accordance with embodiments of the invention. Processes for generating animated video messages using MMS are discussed below.

Animated Video Messages Transmitted Over the Multimedia Messaging Service

0058In many embodiments, networked computing devices can be connected to a cellular data network that can transfer multimedia files via MMS. A process for sending an animated video message over MMS using a server in accordance with an embodiment of the invention is illustrated in <figref idref="DRAWINGS">FIG. 2</figref>. The process <b>200</b> includes receiving (<b>202</b>) an upload request to upload a rendered character facial animation on a server from a networked computing device that utilizes an HTTP post API. The server can be a Multimedia Messaging Service Center (MMSC) server that receives the request as an MMS message encoded in the MMS encapsulation format, defined by the Open Mobile Alliance standard. The encoded MMS message can include the rendered character animation as well as header information including a list of the networked computing devices that are the intended recipients of the message. The server can validate the networked computing device that sent the MMS message, store (<b>204</b>) the content of the MMS message and make the content of the MMS message available via a dynamically generated URL. The server can then generate an MMS notification message, which is sent (<b>206</b>) via a WAP push API over a Short Message Service (SMS) to the networked computing devices that are the intended recipients of the message. The MMS notification message can contain a URL pointer to the MMS content. The server can then receive (<b>208</b>) the request for the rendered character animation from an HTTP get API using the URL pointer and the server can send (<b>210</b>) the rendered character animation to the requesting networked computing device(s).

0059Although specific systems for transmitting animated video messages using MMS are discussed above, animated video messages can be transmitted using a variety of techniques as appropriate to the requirements of specific applications in accordance with embodiments of the invention. Processes for generating animated video messages are discussed below.

Generating Animated Video Messages

0060Animated video messages in accordance with many embodiment of the invention can be generated and transmitted across a system of networked computing devices and servers. Across this network, a variety of configurations of a networked computing device and one or more servers can be utilized to generate an animated video message for display of a rendered character animation based upon interactions with the networked computing device on another networked computing device. Processes that can be performed during the generation and display of animated video messages by a networked computing device that captures video images of a human face and/or animation triggers, and/or a combination of a networked computing device that captures video images of a human face and/or animation triggers, one or more servers, and a networked computing device that displays an animated video message in accordance with embodiments of the invention are discussed further below.

0061A flow chart illustrating a process of generating animated video messages in accordance with an embodiment of the invention is illustrated in <figref idref="DRAWINGS">FIG. 3</figref>. The process <b>300</b> includes capturing (<b>302</b>) video images and/or sensor data indicative of animation triggers. In many embodiments various video images can be captured (<b>302</b>) by a video camera. This video camera can be integrated with or otherwise connected with a networked computing device, such as (but not limited to) a mobile phone, tablet computer or personal computer that can include sensors such as accelerometers, touch screens and/or microphones that can be utilized to capture data to detect animation triggers. From the video images, changes in human facial expressions indicative of human facial animation from a human face captured within the video images can be detected (<b>304</b>). Various different methods of tracking the changes within a human face can be utilized including (but not limited to) tracking landmark points, edges, colors or any aspect of video images from which changes in human facial expressions can be tracked. Optionally, animation triggers can also be recognized (<b>312</b>) that trigger the application of particular behavior or animations to a character in accordance with the particular animation trigger recognized. Character animation can be generated (<b>306</b>) from the tracked changes in human facial expressions as well as motion data applied to the character based upon recognition of an animation trigger. In certain embodiments, character facial animation is generated based upon animating a character with motion data generated using mappings of data tracking changes in human facial expressions across video images. In certain embodiments, character facial animation is generated by mapping changes in a feature vector in a PCA space of human faces and facial expressions derived from the images of human facial expressions to a feature vector in a PCA space for the facial expressions of a 3D character. In other embodiments, any of a variety of techniques can be utilized to track human facial expressions and to map the tracked facial expressions to a facial model of a character. The animation of the character can be rendered (<b>308</b>) into a file as encoded 2D (or 3D) video and decoded for display (<b>310</b>).

0062Although specific processes for generating animated video messages are discussed above, animated video messages can be generated from a variety of processes as appropriate to the requirements of specific applications in accordance with embodiments of the invention. Processes for tracking changes in human facial expressions that can be utilized in generating character facial animations in accordance with embodiments of the invention are discussed below.

Tracking Changes in Video Images of a Human Face

0063In certain embodiments, a human facial expression is identified from a region of a video image identified as representing a human face. In certain embodiments, a human face can be manually identified by a user, such as by a user manually outlining a face in a region of a video image or placing the face in a predetermined location within a video image (e.g. using a template overlaid on a displayed video image). In several embodiments, a cascade of classifiers operating on an image is utilized to detect a human face from within a video image. Various different human face detection methods are discussed in P. Viola, M. Jones, <i>Robust Real</i>-<i>time Object Detection</i>, IJCV 2001, the disclosure of which is hereby incorporated by reference in its entirety. Facial detection methodologies can be enhanced by capturing or processing video images to be more useful. In several embodiments, a conventional RGB video camera can be used to capture video images and each raw video image can undergo image enhancement steps such as, but not limited to, gamma correction, histogram equalization, and shadow recovery. In other embodiments, any of a variety of image enhancement processes that enhance the overall quality of the input image and increase the robustness of subsequent facial expression detection processes within a variable range of lighting conditions and video capture hardware can be utilized.

0064In several embodiments, the process of detecting and tracking human facial expressions involves determining the feature vector from a PCA space of human faces and facial expressions that most closely matches the human face detected within a video image. In certain embodiments, the feature vector changes in a PCA space of human faces and facial expressions is found by determining the feature vector changes in the PCA space of human faces and facial expressions closest to detected changes in human facial expressions. A description of the space of human facial faces and facial expressions can be found by performing PCA with respect to a training set of human faces and facial expressions that are registered with respect to a template. In many embodiments, a training set can include a set of 2D images or 3D images, where the 3D images can include additional metadata including (but not limited to) depth maps. The 3D images contain more information concerning the geometry of the faces in the training dataset. Therefore, defining a PCA space of human faces and facial expressions using 3D geometry information and texture information can be more challenging. Depending upon the training data, the PCA can construct a description of the space of human faces and facial expressions in 2D and/or in 3D. In addition, the training data for human facial expressions can include images of human facial expressions at slight angles relative to the camera and/or images with different light conditions to increase the robustness of the detection of a human facial expression, when a human performer is not looking directly at the camera or when the light conditions vary.

0065The tracking of human facial expressions can then be determined by tracking the feature vector from the PCA space of human faces and facial expressions that best matches the human facial expressions of the detected human face in the video sequence. The space of human faces and human facial expressions can be learned by separating the geometry and texture components of human faces. In many embodiments, the feature vector is a combination of a descriptor of the geometric component of the face (i.e. a vector of a chosen size of coefficients describing facial geometry, for example, as the sum of facial geometry eigenvectors) and a descriptor of a texture component of the face (i.e. a vector of a chosen size of coefficients describing the subject facial texture, for example, as a sum of facial eigenvectors). The feature vector that is the best match can be found by scaling and positioning the face extracted from the captured image with respect to a template and then finding the geometric and texture components of the feature vector within a PCA space of human faces and facial expressions that most closely corresponds to the scaled face.

0066A process for determining the feature vector that most closely matches a human face in accordance with an embodiment of the invention is illustrated in <figref idref="DRAWINGS">FIG. 4</figref>. The process <b>400</b> includes synthesizing (<b>402</b>) a facial geometry from an estimate of face position/size and geometry within a captured video image. A facial texture is then synthesized (<b>404</b>) on a defined reference facial geometry using an estimate of the facial texture based upon the captured image. Optimization (<b>406</b>) of the synthesized geometries and textures can then be performed based upon any of a variety of matching criteria to obtain the geometry and texture that best matches the face in the captured image. In several embodiments, a similarity function (to maximize criteria indicating similarity) or a distance function (to minimize criteria not indicating similarity) are optimized to obtain the geometry and texture that is the best match. Depending upon whether the captured image includes 2D or 3D information, an appropriate 2D or 3D template can be utilized to determine facial geometry.

0067In various embodiments, a human face can be detected and changes tracked through the tracking of landmark points of a face, indicative of human facial expressions, detected within a video image. The changes detected within the human face can then be modeled as the change or movement of these landmark points across video images. Landmark points can be determined manually or through utilization of a process to generate more accurate landmark points, such as but not limited to Active Appearance Models (AAM). Various techniques for utilizing AAM are discussed in T. F. Cootes, G. J. Edwards, C. J. Taylor, <i>Active appearance models</i>, ECCV 1998, the disclosure of which is hereby incorporated by reference in its entirety. In certain embodiments, human facial expressions can be tracked based upon the parameterization of face shape, expression and orientation by using 3 sets of parameters: (1) scale and position of the face in the input video image; (2) a descriptor of the geometric component (a vector of a chosen size of coefficients describing the subject face geometry, for example, as a sum of facial geometry eigenvectors); and (3) a descriptor of the texture component (a vector of a chosen size of coefficients describing the subject facial texture, for example, as a sum of facial texture eigenvectors). In other embodiments, any of a variety of sets of parameters can be utilized to parameterize and track changes in human facial shape, expression and orientation in accordance with embodiments of the invention.

0068Although specific processes for detecting changes in human facial expressions that can be used to generate character facial animation are discussed above, changes in human facial expressions can be detected utilizing any of a variety of processes that are appropriate to the requirements of a specific application in accordance with embodiments of the invention. Processes for generating character facial animation in accordance with embodiments of the invention are discussed below.

Generating Character Facial Animation

0069Character facial animation in accordance with many embodiments of the invention can be generated by mapping a character's facial animation from detected changes in human facial expressions. This mapping determines a relationship (which can be but is not limited to a scaled relationship) between the facial expressions of a human face and the facial expressions of a character. The change of a human face's facial expression over various video images can drive a character facial animation. A process for generating a character facial animation from tracked changes in human facial expressions in accordance with an embodiment of the invention is illustrated in <figref idref="DRAWINGS">FIG. 5</figref>. The process <b>500</b> includes mapping (<b>502</b>) human facial expressions to the facial model of a character. After mapping, changes in human facial expressions can be tracked (<b>504</b>) and used to generate (<b>506</b>) character facial animation in accordance with the mappings.

0070A flow chart illustrating a process of generating a facial expression for a 3D character in accordance with an embodiment of the invention is illustrated in <figref idref="DRAWINGS">FIG. 6</figref>. The process <b>600</b> includes performing (<b>602</b>) PCA to obtain a description of the space of human faces and facial expressions. The process <b>600</b> also includes performing (<b>604</b>) PCA to obtain a description of the space of facial expressions of a 3D character. As an alternative to generating a description of the space of facial expressions of a 3D character, a discrete set of facial expressions can be utilized, the feature vector can be projected into the facial expression controls (such as but not limited to blend shapes controllers) of the 3D character, or a template used in the definition of the PCA space of human faces and facial expressions can be applied to the 3D character face and the feature vector applied directly to the template. After performing PCA to obtain a description of the relevant spaces, a set of mappings is defined that maps (<b>606</b>) the space of human facial expressions to the space of facial expressions of the 3D character. Mappings can include linear, non-linear or a combination of linear and non-linear mappings. After the mappings are generated, the feature vector from the space of human faces and facial expressions that most closely matches a detected face is determined (<b>608</b>). The most closely matching feature vector can then be mapped (<b>610</b>) to a facial expression for the 3D character using the mappings to generate (<b>612</b>) the face of a 3D character including a corresponding facial expression to the human facial expression captured in the image. In the illustrated embodiment, the mapping is between PCA spaces although alternative mappings can also be utilized as appropriate to the requirements of specific applications in accordance with embodiments of the invention.

0071Although specific processes for generating character facial animations are discussed above, processes that generate character facial animation can be implemented in a variety of ways that are appropriate to the requirements of a specific application in accordance with embodiments of the invention. Application of additional animations to characters in response to detection of animation triggers in accordance with embodiments of the invention is discussed further below.

0000Application of Animations from Animation Triggers

0072Animated video messages, in accordance with many embodiments of the invention, can include a character with additional animation applied based upon the recognition of an animation trigger. In certain embodiments, the recognition of an animation trigger applies an additional animation by concatenating the additional animation to existing motion data, layering additional motion data indicative of the additional animation on top of existing motion data, and/or generating an animation that is associated with a character (such as but not limited to a sparking halo that appears on top of a character's head). As discussed above, an animation trigger can be any interaction with a networked computing device that is capable of being recognized by the networked computing device.

0073In several embodiments, animation triggers are based on the recognition of a particular type of interaction with a networked computing device. The interaction can be physical interaction from a user as detected utilizing sensors such as an image capture device, accelerometers, GPS and/or a touch-screen. These physical interactions include any type of physical interaction with a networked computing device such as (but not limited to) physical motions or facial expressions detected by an image capture device, touch user interface (UI) interactions detected on a touchscreen, or motion based interactions such as shaking a networked computer device detected using an accelerometer. The facial expressions can be any facial expressions that can be detected such as a smile or a frown which triggers an additional animation to be applied to a character (such as but not limited to an animation trigger that triggers the overlay of a sparking star animation on a character's tooth). In certain embodiments, the interactions can also be utilized to customize an additional animation applied to a character such as a finger press on a touchscreen used as direct inverse kinematic (IK) effectors applied to a character (such as but not limited to where a user pins the right hand of a character with a finger press while the character is performing some animation that freezes the animation of the character's right hand). In several embodiments, the interactions can also be audio interactions as detected utilizing a microphone. These audio interactions can include semantic interaction, such as the detection of particular spoken words.

0074In several embodiments, physical actions such as gestures performed by a user of a networked computing device can be recognized using machine learning as an animation trigger. These physical actions can include certain physical motions or facial expressions detected by an image capture device or touch user interface (UI) interaction on a touch-screen. Machine learning techniques, such as support vector machines, can be utilized to recognize particular gestures (such as but not limited to a particular type of hand wave or sequence of touch inputs on a touch-screen). Support vector machines are a non-probabilistic binary linear classifier utilized to recognize patterns in the classification of data from a set of training data marked as belonging to particular categories to build a model that assigns new data into categories learned from the training data.

0075In numerous embodiments, an animation trigger can cause an additional animation to be applied to a character as motion data indicative of the additional animation. The motion data can be blended with other motion data to affect the animation of a character in real time. Furthermore, multiple animation triggers can simultaneously trigger the application of motion data indicative of a number of additional animations that can be blended together to animate a character.

0076In many embodiments, an animation trigger can cause an additional animation to be concatenated to an existing character animation to generate a new sequence of animations. An additional animation can be concatenated by generating a transition between a motion and the additional motion by modifying and/or adding additional motion data to generate a smooth animation sequence. In certain embodiments, the transition between the two sets of motion data can be iteratively refined until an acceptable transition is obtained. Various techniques for concatenating and blending character animation are discussed further in U.S. patent application Ser. No. 13/097,031 filed Aug. 28, 2011, titled “REAL-TIME AUTOMATIC CONCATENATION OF 3D ANIMATION SEQUENCES”, the disclosure of which is incorporated herein by reference in its entirety.

0077A flow chart illustrating the application of animations to an animated video message in accordance with an embodiment of the invention is illustrated in <figref idref="DRAWINGS">FIG. 7</figref>. The process <b>700</b> includes recognizing (<b>702</b>) an animation trigger. An additional animation can be selected (<b>704</b>) based upon the recognized animation trigger. The additional animation can then be applied (<b>706</b>) to a character to generate (<b>708</b>) character animation with the additional animation.

0078In many embodiments, the animations are combined with the assistance of similarity maps that identify pose similarity between the two sets of motion data. In several embodiments, the similarity map can be weighted to prioritize similarity between key components of a character. The similarity map can be utilized to generate a combined animation using combination processes including but not limited to a combination of motion blending; linear or non-linear time warping; physics considerations such as conservation of momentum or speed; pose matching elements such as matching of the pivot node position and or orientation; and inverse kinematic constraints. Generating a combined animation can start with the spatial registration and time-warping of the first and additional motions using defined parameters, such as using a foot or the hips as a registration point. Then blending between the frames of the first motion and frames of the additional motion can be computed. Further corrections and/or improvements can be applied to the blended motion, including but not limited to time-warping correction, smoothness enforcement, and corrections accounting for conservation of momentum or speed. A number of controls can be open to user's interaction for fine tuning of the motions for 3D character animation.

0079Although specific processes for applying additional animations and combining motion data of multiple animations are discussed above, processes for generating character animation and for generating animated video messages can be implemented in a variety of ways that are appropriate to the requirements of specific applications in accordance with embodiments of the invention. Rendering and display of animated video messages are discussed further below.

Rendering and Display of Animated Video Messages

0080Animated video messages in accordance with many embodiments of the invention can be rendered using an animation of a character and the rendered video displayed on a networked computing device. The term rendering is typically used to describe calculations performed by a processor to translate a mathematical description of a scene into 2D video image data. During the rendering process, all the data related to a scene including (but not limited to) spatial, textural and lighting information is combined to determine the values of each pixel within a flattened image. Animated video messages can be rendered as video image data that can be displayed on a networked computing device and/or encoded for storage, transmission and/or decoding on another networked computing device. Video image data can be generated from a scene file that includes information that represents a character's animation in virtual space with additional details such as (but not limited to) geometry, backdrop, props, viewpoint, texture, lighting and shading information from which scenes in their entirety (which include character facial animation) can be represented. In certain embodiments, rendering generates a scene that includes an effect where character animation is overlaid over other video images such as (but not limited to) the images of a human face utilized to drive the animation of the facial model. In many embodiments, a scene file can be shared between different networked computing devices and the users of the networked computing devices can collaboratively modify the contents of the scene.

0081In several embodiments, animated content is transferred as metadata from one networked computing device to another networked computing device. A software application can be installed in both networked computing devices that enable transmission of a full 3D scene as opposed to 2D rendered video or a rendered multiview stereo pair of video streams. The recipient networked computing device can thus experience the animated message in a 3D scene and facilitate interactions with content, such as (but not limited to) by controlling the 3D scene camera position and/or orientation. In a number of embodiments, the software application can enable the addition of further animations and/or the forwarding of the animated message to other networked computing devices.

0082Side by side screenshots displaying an animated video message and the video images from which the animated video message is derived are illustrated in <figref idref="DRAWINGS">FIGS. 8A, 8B and 8C</figref>. <figref idref="DRAWINGS">FIG. 8A</figref> illustrates an animated video message <b>802</b> generated from a surprised human facial expression <b>804</b> captured within a video image. Similarly, <figref idref="DRAWINGS">FIG. 8B</figref> illustrates an animated video message <b>822</b> generated from an angry human facial expression <b>824</b> captured within a video image. Lastly, <figref idref="DRAWINGS">FIG. 8B</figref> illustrates an animated video message <b>842</b> generated from a neutral human facial expression <b>844</b> captured within a video image.

0083Although specific processes for rendering and display of animated video messages are discussed above, processes for rendering and display of animated video messages can be implemented in a variety of ways that are appropriate to the requirements of specific applications in accordance with embodiments of the invention. In many embodiments, the ability to collaboratively create animated video messages can be utilized in the collaborative creation of animated content and interactive animated video messages. Interactive animated video messages and processes for collaboratively creating animated video messages and interactive animated video messages in accordance with embodiments of the invention are discussed further below.

Interactive Animated Video Messages

0084Systems for generating animated video messages in accordance with many embodiments of the invention enable the collaborative creation of animated messages using multiple stages of sharing and distribution of content. In addition to modifying animations and content within an animated video message, systems for generating animated video messages can enable users to reuse, extend or augment portions of animated video messages for the purpose of creating additional content. In several embodiments, alternative animation sequences can be included in a single animated message to enable the interactive playback of the animated content based upon user selections. As can readily be appreciated, interactive animated messages are rich with content that can also be reused, extended or augmented to create additional animated content.

0085An interactive animated video message in accordance with an embodiment of the invention is conceptually illustrated in <figref idref="DRAWINGS">FIG. 9</figref>. The interactive animated video message <b>900</b> includes six groupings (<b>902</b>) of animation sequences that can each be considered an act within the interactive animated video message. A user can select one (<b>904</b>) of the set of animation sequences in each act to cause the rendering and/or playback of a video sequence based upon the selections. In this way, a single interactive animated video message can be played back in a variety of different ways. In several embodiments, the playback of an interactive animated video message can be randomized. In many embodiments, a user that wishes to send an animated video message that is not interactive can effectively extract an animated video message from the content contained within the animated video message. As is the case with a non-interactive video message, the user can also extract a specific animation sequence from the interactive animated video message for reuse in another animated video message.

0086Although a specific interactive video message is illustrated in <figref idref="DRAWINGS">FIG. 9</figref>, any of a variety of interactive animated video messages and/or interactive video content can be generated in which alternative pieces of content are provided and the playback of content can be determined based upon user interaction including (but not limited) interactive video content including fewer or a greater number of acts, fewer or a greater number of alternative animation sequences and/or rendered video clips, and/or acts in which no alternative content is provided in accordance with embodiments of the invention. Processes for collaboratively generating animated video messages and content throughout the social graph through the use of animation sequences and/or video clips contained within animated video messages in accordance with embodiments of the invention are discussed further below.

Collaborative Message Creation

0087Animated video messages can be created collaboratively and animation sequences, and/or video clips within an animated video message can be further reused, extended or augmented to create additional animated video messages. In this way, various animation sequences can be seeded into the social graph and can become building blocks for the creation of an increasing array of content.

0088The propagation of animation sequences within animated video messages and the reuse of the animation sequences to create additional content using systems for generating animated video messages in accordance with an embodiment of the invention is conceptually illustrated in <figref idref="DRAWINGS">FIG. 10</figref>. The term social graph is used to describe a graph or data structure that describes personal relationships of users of a system. Many services including the Facebook service provided by Facebook, Inc. of Menlo Park, Calif. can enable the spread of content and information utilizing a social graph. Systems for generating animated video messages in accordance with embodiments of the invention can tap into a social graph to enable the distribution of animated video messages. In several embodiments, users <b>1002</b> distribute animated video messages <b>1004</b> to other users <b>1002</b> and reuse animation sequences within the animated video messages to create new animated video messages. With specific reference to the distribution of animated video messages shown in <figref idref="DRAWINGS">FIG. 10</figref>, the manner in which a single animation sequence <b>1006</b> that is part of an interactive video message is reused is illustrated. The five users <b>1002</b> each generate animated video messages and users U<b>2</b>-U<b>5</b> generate animated video messages that incorporate the video sequence <b>1006</b> contained within the interactive animated video message distributed by U<b>1</b> and/or a version of the video sequence modified using any of techniques described above. As can readily be appreciated, distribution of animated video messages in the manner illustrated in <figref idref="DRAWINGS">FIG. 10</figref> via the social graph can result in the seeding of the social graph with a large number of animation sequences that can be reused by other users to generate animated video messages.

0089Although the above discussion of distribution of video messages and reuse, extension or augmentation of video sequences and/or video clips in relation to <figref idref="DRAWINGS">FIG. 10</figref> is presented in the context of users of a social graph, systems for generating animated video messages can leverage the ad hoc social graph formed by the contacts that users maintain in email accounts, within other contact lists on mobile phones and messaging services, and/or within a animated video messaging application. Accordingly, the collaborative creation of animated video messages and the reuse, extension or augmentation of video sequences in the creation of animated video messages is not limited to systems that require distribution of animated video messages utilizing a social graph.

0090While the above description contains many specific embodiments of the invention, these should not be construed as limitations on the scope of the invention, but rather as an example of one embodiment thereof. It is therefore to be understood that the present invention may be practiced otherwise than specifically described, without departing from the scope and spirit of the present invention. Thus, embodiments of the present invention should be considered in all respects as illustrative and not restrictive. Accordingly, the scope of the invention should be determined not by the embodiments illustrated, but by the appended claims and their equivalents.