Keywords: MPEG-4, face animation, computer graphics, deformation, VRML, speech synthesizer, electronic commerce

1. Introduction

   MPEG-4 is an object-based multimedia compression standard, which allows for encoding of different audio-visual objects (AVO) in the scene independently. The visual objects may have natural or synthetic content, including arbitrary shape video objects, special synthetic objects such as human face and body, and generic 2-D/3-D objects composed of primitives like rectangles, spheres, or indexed face sets, which define an object surface by means of vertices and surface patches. The synthetic visual objects are animated by transforms and special purpose animation techniques, such as face/body animation and 2D-mesh animation. MPEG-4 also provides synthetic audio tools such as structured audio tools and a text-to-speech interface (TTSI). This paper presents a detailed overview of synthetic visual objects supported by MPEG-4 version-1, namely animated faces and animated arbitrary 2-D uniform and Delaunay meshes. We also address integration of the face animation tool with the TTSI, so that face animation can be driven by text input. Body animation and 3-D mesh compression and animation will be supported in MPEG-4 version-2, and hence are not covered in this article.

   The representation of synthetic visual objects in MPEG-4 is based on the prior VRML standard [13][12][11] using nodes such as Transform, which defines rotation, scale or translation of an object, and IndexedFaceSet describing 3-D shape of an object by an indexed face set. However, MPEG-4 is the first international standard that specifies a compressed binary representation of animated synthetic audio-visual objects. It is important to note that MPEG-4 only specifies the decoding of compliant bit streams in an MPEG-4 terminal. The encoders do enjoy a large degree of freedom in how to generate MPEG-4 compliant bit streams. Decoded audio-visual objects can be composed into 2D and 3D scenes using the Binary Format for Scenes (BIFS) [13], which also allows implementation of animation of objects and their properties using the BIFS-Anim node. We recommend readers to refer to an accompanying article on BIFS for the details of implementation of BIFS-Anim. Compression of still textures (images) for mapping onto 2D or 3D meshes is also covered in another accompanying article. In the following, we cover the specification and compression of face animation and 2D-mesh animation in Sections 2 and 3, respectively.

2. Face Animation

   MPEG-4 foresees that talking heads will serve an important role in future customer service applications. For example, a customized agent model can be defined for games or web-based customer service applications. To this effect, MPEG-4 enables integration of face animation with multimedia communications and presentations and allows face animation over low bit rate communication channels, for point to point as well as multi-point connections with low-delay. With AT&T’s implementation of an MPEG-4 face animation system, we can animate a face models with a data rate of 300 - 2000bits/s. In many applications like Electronic Commerce, the integration of face animation and text to speech synthesizer is of special interest. MPEG-4 defines an application program interface for TTS synthesizer. Using this interface, the synthesizer can be used to provide phonemes and related timing information to the face model. The phonemes are converted into corresponding mouth shapes enabling simple talking head applications. Adding facial expressions to the talking head is achieved using bookmarks in the text. This integration allows for animated talking heads driven just by one text stream at a data rate of less than 200 bits/s [22]. Subjective tests reported in [26] show that an Electronic Commerce web site with talking faces gets higher ratings than the same web site without talking faces. In an amendment to the standard foreseen in 2000, MPEG-4 will add body animation to its tool set thus allowing the standardized animation of complete human bodies.

   In the following sections, we describe how to specify and animate 3D face models, compress facial animation parameters, and integrate face animation with TTS in MPEG-4. The MPEG-4 standard allows using proprietary 3D face models that are resident at the decoder as well as transmission of face models such that the encoder can predict the quality of the presentation at the decoder. In Section 2.1, we explain how MPEG-4 specifies a 3D face model and its animation using face definition parameters (FDP) and facial animation parameters (FAP), respectively. Section 2.2 provides details on how to efficiently encode FAPs. The integration of face animation into an MPEG-4 terminal with text-to-speech capabilities is shown in Section 2.3. In Section 2.4, we describe briefly the integration of face animation with MPEG-4 systems. MPEG-4 profiles with respect to face animation are explained in Section 2.5.

   1. Specification and Animation of Faces

      MPEG-4 specifies a face model in its neutral state, a number of feature points on this neutral face as reference points, and a set of FAPs, each corresponding to a particular facial action deforming a face model in its neutral state. Deforming a neutral face model according to some specified FAP values at each time instant generates a facial animation sequence. The FAP value for a particular FAP indicates the magnitude of the corresponding action, e.g., a big versus a small smile or deformation of a mouth corner. For an MPEG-4 terminal to interpret the FAP values using its face model, it has to have predefined model specific animation rules to produce the facial action corresponding to each FAP. The terminal can either use its own animation rules or download a face model and the associated face animation tables (FAT) to have a customized animation behavior. Since the FAPs are required to animate faces of different sizes and proportions, the FAP values are defined in face animation parameter units (FAPU). The FAPU are computed from spatial distances between major facial features on the model in its neutral state.

      In the following, we first describe what MPEG-4 considers to be a generic face model in its neutral state and the associated feature points. Then, we explain the facial animation parameters for this generic model. Finally, we show how to define MPEG-4 compliant face models that can be transmitted from the encoder to the decoder for animation.

      1. MPEG-4 Face Model in Neutral State

1. Coding of Face Animation Parameters

   MPEG-4 provides two tools for coding of facial animation parameters. Coding of quantized and temporally predicted FAPs using an arithmetic coder allows for low delay FAP coding (Section 2.2.1). Alternatively, discrete cosine transform (DCT) coding of a sequence of FAPs introduces a larger delay but achieves higher coding efficiency (Section 2.2.2).

   MPEG-4 provides a special mode (def_bit) that allows downloading definitions of expressions and visemes (FAP 1 and 2) in terms of low-level FAPs. Although the syntax for this capability is defined, MPEG-4 does not require the decoder to store a minimum number of these definitions. Therefore we recommend not using this tool until MPEG-4 provides clarifications on this tool in a potential future revision of the standard. Instead, we recommend the use of the FAP Interpolation Table (FIT) as described in Section 2.2.3.

   1. Arithmetic Coding of FAPs

      igure 9 shows the block diagram for low delay encoding of FAPs. The first set of FAP values FAP₀ at time instant 0 with is coded without prediction (intra coding). The value of a FAP at time instant k FAP_k is predicted using the previously decoded value FAP'_k-1. The prediction error e is quantized using a quantization step size QP that is specified in Table 7 multiplied by a quantization parameter FAP_QUANT with 0<FAP_QUANT<31. FAP_QUANT is identical for all FAP values at one time instant k. Using the FAP dependent quantization step size QP,× FAP_QUANT assures that quantization errors are subjectively evenly distributed between different FAPs. The quantized prediction error e’ is arithmetically encoded using a separate adaptive probability model for each FAP. Since the encoding of the current FAP value depends only on one previously coded FAP value, this coding scheme allows for low-delay communications. At the decoder, the received data is arithmetically decoded, dequantized and added to the previously decoded value in order to recover the encoded FAP value. When using FAP_QUANT>15, the subjective quality of the animation deteriorates significantly such that we recommend not to increase FAP_QUANT above 15 [21].

       

      

      Figure 9: Block diagram of the low delay encoder for FAPs.

      In order to avoid transmitting all FAPs for every frame, the encoder can transmit a mask indicating for which groups (Table 2) FAP values are transmitted. The encoder can also specify for which FAPs within a group values will be transmitted. This allows the encoder to send incomplete sets of FAPs to the decoder. FAP values that have been initialized in an intra coded FAP set are assumed to retain those values if subsequently no update is transmitted. However, the encoder can also signal to the decoder that a previously transmitted FAP value is not valid anymore.

      The decoder can extrapolate values of FAPs that have been invalidated or have never been specified, in order to create a more complete set of FAPs. The standard provides only limited specifications on how the decoder is supposed to extrapolate FAP values. Examples are that if only FAPs for the left half of a face are transmitted, the corresponding FAPs of the right side have to be set such that the face moves symmetrically. If the encoder only specifies motion of the inner lip (FAP group 2), the motion of the outer lip (FAP group 8) has to be extrapolated in an unspecified way. Letting the decoder extrapolate FAP values may create unexpected results depending on the particular decoder. However, the encoder can always prevent the decoder from using extrapolation by defining all FAP values or defining FAP Interpolation Tables (Section 2.2.3).

   2. DCT Coding of FAPs

      The second tool that is provided for coding FAPs is the discrete cosine transform applied to 16 consecutive FAP values. This introduces a significant delay into the coding and decoding process. Hence, this coding method is mainly useful for applications where animation parameter streams are retrieved from a database. After computing the DCT of 16 consecutive values of one FAP, DC and AC coefficients are coded differently (Figure 10). Whereas the DC value is coded predictively using the previous DC coefficient as prediction, the AC coefficients are directly coded. The AC coefficient and the prediction error of the DC coefficient are linearly quantized. Whereas the quantizer step size can be controlled, the ratio between the quantizer step size of the DC coefficients and the AC coefficients is set to ¼. The quantized AC coefficients are encoded with one variable length code word (VLC) defining the number of zero-coefficients prior to the next non-zero coefficient and one VLC for the amplitude of this non-zero coefficient. The handling of the decoded FAPs with respect to masking and interpolation is not changed (see Section 2.2.1).

      

      Figure 10: Block diagram of the FAP encoder using DCT. DC coefficients are predictively coded. AC coefficients are directly coded (from [23]).

      Figure 11 compares the coding performance of the DCT FAP coder and the arithmetic FAP coder. The PSNR is measured by comparing the amplitude of the original and coded FAP averaging over all FAPs. This PSNR does not relate to picture quality but to the smoothness of temporal animation. In contrast to the arithmetic coder, the DCT coder is not able to code FAPs with near lossless quality. At low data rates, the DCT coder requires up to 50% less data rate than the arithmetic coder at the price of an increased coding delay. This advantage in coding efficiency disappears with increasing fidelity of the coded parameters.

      

      Figure 11: Rate distortion performance of the arithmetic and DCT coding mode of FAPs for the sequences Marco30 (30 Hz) and Expressions (25 Hz) (from [21]).

   3. FAP Interpolation Tables

1. Integration of Face Animation and Text-to-Speech Synthesis

   MPEG-4 provides interfaces for a proprietary text-to-speech (TTS) synthesizer [15] that allow driving a talking head from text (see Figure 13) [5][6][8][18][1][2]. This section discusses the integration of face animation and TTS [3] allowing for animation of a talking face using a TTS synthesizer [22]. A key issue here is the synchronization of the speech stream with the FAP stream. Synchronization of a FAP stream with TTS synthesizers using the TTS Interfaces (TTSI) is only possible, if the encoder sends prosody and timing information. This is due to the fact that a conventional TTS system driven by text only behaves as an asynchronous source.

   Given a TTS stream that contains text or prosody in binary form, the MPEG-4 TTSI decoder decodes the gender, text and prosody information according to the interface defined for the TTS synthesizer. The synthesizer creates speech samples that are handed to the compositor. The compositor presents audio and if required video to the user. The second output interface of the synthesizer sends the phonemes of the synthesized speech as well as start time and duration information for each phoneme to the Phoneme/Bookmark-to-FAP-Converter [22]. The converter translates the phonemes and timing information into face animation parameters that the face renderer uses in order to animate the face model. The precise method of how the converter derives visemes from phonemes is not specified by MPEG and left to the implementation of the decoder. This also allows using a coarticulation model at the decoder that uses the current, previous and next phoneme in order to derive the correct mouth shape.

   Most speech synthesizers do not have a synchronous behavior. This means that the time they require to speak a sentence in not predictable. Therefore, synchronizing the output of a TTS with facial expressions defined in a FAP stream is not possible. Bookmarks in the text of the TTS are used to animate facial expressions and non-speech-related parts of the face [22]. The start time of a bookmark is derived from its position in the text. When the TTS finds a bookmark in the text it sends this bookmark to the Phoneme/Bookmark-to-FAP-Converter at the same time as it sends the first phoneme of the following word. The bookmark defines the start point and duration of the transition to a new FAP amplitude. Consequence: No additional delay, no look ahead in the bit stream but no precise timing control on when the amplitude will be reached relative to the spoken text.

   An example of a TTS stream with bookmarks is given in Figure 14 [22]. The renderer will generate the visemes associated with each word, following the timing information derived by the speech synthesizer. It will also start to deform the model to generate a smile with an amplitude of 40. To simulate a more natural expression, which typically goes through three phases (onset, climax, and relax), a desired temporal behavior [20][23] for a prescribed FAP can be specified in the bookmark. Three functions are defined: A linear interpolation function and a Hermite function can be used to specify the transition of a FAP from its current value to the target value. A triangular function can be specified to linearly increase the amplitude of a FAP to the target value and to decrease it back to its starting amplitude. The bookmark also specifies the desired duration to reach the FAP value in the bookmark. If another bookmark appears before this duration, the renderer starts to deform the face according to the newly specified FAP information from the current position. This is illustrated in Figure 14 using Hermite functions.

   

   Figure 13: Block diagram showing the integration of a proprietary Text-to-Speech Synthesizer into an MPEG-4 face animation system.

   

   Figure 14: Example for text with bookmarks for one facial expression (joy) and the related amplitude of the animated FAP. The syntax of a bookmark is: <FAP 2 (expression) 1 (joy) amplitude 1 (joy) amplitude duration 3 (Hermite time curve)>. The amplitude of joy over time is computed according to the bookmarks (see Section 2.1.2).

2. Integration with MPEG-4 Systems

   In order to use face animation in the context of MPEG-4 systems, a BIFS scene graph has to be transmitted to the decoder. The minimum scene graph contains a Face node and a FAP node. The FAP decoder writes the amplitude of the FAPs into fields of the FAP node. The FAP node might have the children Viseme and Expression which are FAPs requiring a special syntax (see Section 2.1.2). This scene graph would enable an encoder to animate the proprietary face model of the decoder. If a face model is to be controlled from a TTS system, an AudioSource node is to be attached to the face node.

   In order to download a face model to the decoder, the face node requires an FDP node as one of its children. This FDP node contains the position of the feature points in the downloaded model, the scene graph of the model and the FaceDefTable, FaceDefMesh and FaceDefTransform nodes required to define the action caused by FAPs. Figure 15 shows how these nodes relate to each other.

   

   Figure 15: Nodes of a BIFS scene graph that are used to describe and animate a face. The FaceSceneGraph contains the scene graph of the static face. Here, it is assumed that the streams are already decoded.

3. MPEG-4 Profiles for Face Animation

1. 2D Mesh Animation

   MPEG-4 version-1 supports 2D uniform or content-based (nonuniform) Delaunay triangular mesh representation of arbitrary visual objects, that includes an efficient method for animation of such meshes. A simplified block diagram of an MPEG-4 encoder/decoder supporting the 2D-mesh object is depicted in Figure 16, where the 2D-mesh object can be used together with a video object or a still-texture object encoder/decoder. We present the basic concepts of 2D-mesh representation and animation in Section 3.1. Mesh analysis, discussed in Section 3.2, refers to design or specification of 2D mesh data for video object editing or still-texture animation. Section 3.3 describes 2D-mesh object coding in detail. Finally, applications of 2D mesh in video object editing and still texture animation are presented in Section 3.4.

   

   Figure 16: Simplified architecture of an encoder/decoder supporting the 2D-mesh object. Mesh analysis module extracts the 2D mesh data, which is then encoded by the mesh encoder. The coded mesh representation is embedded in a BIFS elementary stream. At the receiver, the 2D-mesh decoder is invoked automatically by the BIFS-Anim node.

   1. 2D Mesh Representation and Animation

      A 2D triangular mesh (or a mesh object plane) is a planar graph that tessellates (partitions) a video object plane or its bounding box into triangular patches. The vertices of each patch are called node points. A 2D mesh object, which consists of a sequence of mesh object planes (MOPs), is compactly represented by mesh geometry at some key (intra) MOPs and mesh motion vectors at all other (inter) MOPs. The mesh geometry refers to the location of the node points on the key mesh object planes. 2D mesh animation is accomplished by propagating the 2D mesh defined on key MOPs using one motion vector per node point per object plane until the next key MOP. Both mesh geometry and motion (animation) information are predictively coded for an efficient binary representation. The mesh topology is always either uniform or Delaunay, hence there is no need for topology compression. (The reader is referred to [28] for an introduction to Delaunay meshes.)

      Mesh-based motion modeling differs from block-based motion modeling (that is used in natural video object coding) in that the triangular patches overlap neither in the reference frame nor in the current frame. Instead, triangular patches in the current frame are mapped onto triangular patches in the reference frame, and the texture inside each patch in the reference frame is warped onto the current frame using a parametric mapping, such as affine mapping, as a function of the node point motion vectors. This process is called texture mapping, which is an integral part of mesh animation. The affine mapping between coordinates (x’,y’) at time t’ and (x, y ) at time t is given by [27]

      (2)

      where a_i are the affine motion parameters. The six degrees of freedom in the affine mapping matches that of warping a triangle by the motion vectors of its three vertices (with two degrees of freedom in each). Furthermore, if proper constraints are imposed in parameter (node motion vector) estimation, an affine transform can guarantee the continuity of the mapping across the boundaries of adjacent triangles. Thus, 2D mesh modeling corresponds to non-uniform sampling of the motion field at a number of salient feature points (node points), from which a continuous, piece-wise affine motion field can be reconstructed. The fact that the mesh structure constrains movements of adjacent image patches has certain advantages and disadvantages: Meshes are well-suited to represent mildly deformable but spatially continuous motion fields. However, they do not allow discontinuities in the motion field; thus, cannot easily accommodate articulated motions and self-occlusions.

   2. 2D Mesh Analysis

      The design of the mesh data associated with a video object or animation is an encoder issue, and hence is not normative. This section discusses an example procedure for the reader’s information, where we design either uniform or content-based meshes for intra MOPs and track them to determine the inter MOPs. The block diagram of the procedure is depicted in Figure 17. The first box is explained in Section 3.2.1, and the next four in Section 3.2.2.

      

      Figure 17: The 2D mesh design and tracking procedure. The feedback loop increments the frame counter. The process is re-initialized (i.e., a new intra MOP is inserted) if model failure region exceeds a threshold or a scene change is detected.

      1. Mesh Design for Intra MOPs

         Intra meshes are either uniform or content-based. A uniform mesh is designed over a rectangular region, which is generally the bounding box of the VOP. It is specified in terms of five parameters: the number of nodes in the horizontal and vertical directions, the horizontal and vertical dimension of each rectangular cell in half pixel units, and the triangle split code that specifies how each cell is divided into two triangles (see Section 3.3.1.1). As a rule of thumb, we target the total number of triangles over the bounding box to be equal to that of the macroblocks that would be obtained in natural VOP coding. A content-based mesh may be designed to fit exactly on the corresponding VOP. The procedure consists of three steps: i) Approximation of the VOP contour by a polygon through selection of N_b boundary node points; ii) selection of N_i interior node points; and iii) Delaunay triangulation to define the mesh topology. There are various methods for approximation of arbitrary shaped contours by polygons [33][35]. Interior node points may be selected to coincide with high-gradient points or corner points within the VOP boundary [33]. An example of a content-based mesh is depicted in Figure 18.

         

         Figure 18: A content-based mesh designed for the "Bream" video object.

      2. Mesh Tracking

      Motion data of the 2D mesh may represent the motion of a real video object (for natural video object compression and manipulation applications) or may be synthetic (for animation of a still texture map). In the former case, the motion of a natural video object may be estimated by forward mesh tracking. The latter requires special purpose tools and/or artistic skills. In forward mesh tracking, we search in the current video object plane for the best matching locations of the node points of the previous (intra or inter) mesh, thus tracking image features until the next intra MOP. The procedure applies for both uniform and content-based meshes.

      Various techniques have been proposed for node motion estimation for forward mesh tracking. The simplest method is to form blocks that are centered around the node points and then employ a closed-form solution or block-matching to find motion vectors at the node points independently [27][29]. Alternatively, hexagonal matching  [30] and closed-form matching [31] techniques find the optimal motion vector at each node under the parametric warping of all patches surrounding the node while enforcing mesh connectivity constraints at the expense of more computational complexity. Another method is iterative gradient-based optimization of node point locations, taking into account image features and mesh deformation criteria[32]. Hierarchical tracking methods may provide significantly improved performance and robustness in enforcing constraints to avoid foldovers [34][36]. We also recently proposed a semi-automatic (interactive) tool for accurate mesh object tracking [37].

   3. 2D Mesh Object Encoding/Decoding

      Mesh data consists of a list of node locations (x_n, y_n) where n is the node index (n=0,¼ ,N-1) and a list of triangles t_m where m is the triangle index (m = 0, ..., M-1). Each triangle t_m is specified by a triplet <i, j, k> of the indices of the node points that are the vertices of that triangle. The syntax of the compressed binary representation of intra and inter MOPs and the semantics of the decoding process is normative in MPEG-4. Each MOP has a flag that specifies whether the data that follows is geometry data (intra MOP) or motion data (inter MOP). A block diagram of the decoding process is shown in Figure 19. Mesh geometry decoding computes the node point locations and reconstructs a triangular mesh from them. Mesh motion decoding computes the node motion vectors and applies them to the node points of the previous mesh to reconstruct the current mesh. The reconstructed mesh is stored in the mesh data memory, so that it can be used in motion decoding of the next MOP. In the following, we first describe the decoding of mesh geometry, and then the mesh motion. We assume a pixel-based 2D coordinate system, where the x-axis points to the right from the origin, and the y-axis points down from the origin.

      

      Figure 19: Simplified block diagram of 2D Mesh Object decoding.

      1. Encoding/Decoding of Mesh Geometry

         The flag mesh_type_code specifies whether the topology of an intra MOP is uniform or Delaunay. In either case, the coded geometry information, described in detail in the following, defines the 2D mesh uniquely so that there is no need for explicit topology compression.

         1. Uniform Mesh

            A 2D uniform mesh can be viewed as a set of rectangular cells, where each rectangle is split into two triangles. Five parameters are used to specify the node point locations and topology of a uniform mesh. The top-left node point of the mesh always coincides with the origin of a local coordinate system. The first two parameters specify the number of nodes in the horizontal and vertical direction of the mesh, respectively. The next two parameters specify the horizontal and vertical size of each rectangular cell in half pixel units. This completes the layout and dimensions of the mesh. The last parameter specifies how each rectangle is split to form two triangles: four choices are allowed as illustrated in Figure 20. An example of a 2D uniform mesh is given in Figure 21.

            

            Figure 20: Types of uniform mesh topology: Code 00 - top-left to right bottom; Code 01 - bottom-left to top right; Code 10 – alternate between top-left to bottom-right and bottom-left to top-right; Code 11 – alternate between bottom-left to top-right and top-left to bottom-right.

            

            Figure 21: Example of a uniform 2D mesh specified by five parameters, where nr_mesh_nodes_hor is equal to 5, nr_mesh_nodes_vert is equal to 4, mesh_rect_size_hor and mesh_rect_size vert are specified as shown, and the triangle_split_code is equal to ‘00’.

         2. Delaunay Mesh

         A 2D Delaunay mesh is specified by the following parameters: i) The total number of node points N; ii) the number of node points N_b that are on the boundary of the mesh; and iii) the coordinates , n=0, ¼ , N-1, of all node points. The origin of the local coordinate system is assumed to be at the top left corner of the bounding box of the mesh. Note that the number of nodes in the interior of the mesh N_i can be computed as

         (3)

         The first node point, , is decoded directly, where the coordinates and are specified with respect to the origin of the local coordinate system. All other node points are computed by adding the decoded values and to the x- and y-coordinates, respectively, of the last decoded node point as follows

         (4)

         The first N_b node point coordinates that are encoded/decoded must correspond to the boundary nodes in order to allow their identification without additional overhead. Thus, after receiving the first N_b locations, the decoder can reconstruct the boundary of the mesh by connecting each pair of successive boundary nodes, as well as the first and the last, by straight-line edge segments. This is illustrated with an example in Figure 22.

         

         Figure 22: Decoded node points and reconstruction of mesh boundary.

         The next N_i coordinate values define the interior node points. Finally, the mesh is reconstructed by applying constrained Delaunay triangulation to all node points, where the boundary polygon forms the constraint. Constrained triangulation of node points contains triangles only to the interior of the region defined by the boundary segments. Furthermore, each triangle of a constrained Delaunay triangulation satisfies the property that the circumcircle of does not contain any node point visible from all three vertices of . A node point is visible from another node point if a straight line between them falls entirely inside or exactly on the constraining polygonal boundary. An example of a mesh obtained by constrained triangulation of the node points in Figure 22 is shown in Figure 23.

         

         Figure 23: Decoded triangular mesh obtained by constrained Delaunay triangulation.

      2. Encoding/Decoding of Mesh Motion

         An inter MOP is defined by a set of 2D motion vectors that are associated with each node point of the previous MOP. We can then reconstruct the locations of node points in the current MOP by propagating the corresponding node of the previous MOP. The triangular topology of the mesh remains the same until the next intra MOP. Node point motion vectors are decoded predictively, i.e., the components of each motion vector are predicted using those of two previously decoded node points determined according to a breadth-first traversal as described in Section 3.3.2.1. Section 3.3.2.2 describes the prediction process.

         1. Mesh Traversal

1. Motion Vector Prediction

   The mesh motion bitstream is composed of prediction error vectors , whose components are variable length coded. The ordering of the triangles defines the order in which the motion vector data of each node point is encoded/decoded, as described in the following. First, motion vector data for the top-left node n₀ of the mesh is retrieved from the bitstream. No prediction can be used in coding the motion vector of n₀. Hence,

   (5)

   Then, the prediction error vector e_n1 for the next clockwise node on the boundary with respect to the top-left node is retrieved from the bitstream. Note that only v_n0 can be used to predict v_n1. That is,

   (6)

   We mark these first two nodes (that form the base edge of the initial triangle) with the label ‘done’. At this point the two nodes on the base edge of any triangle in the sequential order as defined in Section 3.3.2.1 are guaranteed to be labeled ‘done’ (indicating that their motion vectors have already been decoded and may be used as predictors) when we reach that triangle. Then, for each triangle, the motion vectors of the two nodes of the base edge are used to form a prediction for the motion vector of the third node. If that third node is not already labeled ‘done’, the prediction vector is computed by averaging the two motion vectors, as follows:

   (7)

   and its motion vector is given by

   (8)

   Consequently, the third node is also labeled ‘done’. If the third node is already labeled ‘done’, then it is simply ignored and we proceed to the next triangle. Note that the prediction error vector is specified only for node points with a nonzero motion vector. Otherwise, the motion vector is simply . Finally, the horizontal and vertical components of mesh node motion vectors are processed to lie within a certain range, as in the case of video block-motion vectors.

2. An Example

1. Integration with MPEG-4 Systems

   2D mesh geometry and motion data are passed on to an IndexedFaceSet2D node using the BIFS animation-stream for rendering and/or texture mapping (see the paper on BIFS in this issue). BIFS animation is a general framework for streaming parameters to certain fields of some BIFS nodes. Suppose a node (describing an object) is below a Transform node in the scene description tree. We can then animate the position of this object using BIFS-Anim by streaming a sequence of x, y, z positions to the 'translation' field of the Transform node. In this case, the x, y, z positions are quantized and encoded by an arithmetic coder. Both 2D mesh animation and face animation are special cases of BIFS-Anim in that the coding of the respective animation parameters is specified in the Visual part of MPEG-4. These coded bitstreams are just wrapped into the BIFS-Anim stream.

   In order to use the BIFS-Anim framework, we need to define an AnimationStream node in the scene, which points to the encoded parameter stream using an object-descriptor (just like in the case of a video-stream). The animation-stream decoder knows where to pass this data by means of a unique node-ID, e.g., that of the IndexedFaceSet2D node, which must be specified when setting up the animation-stream. From the node-ID, the animation-stream decoder can infer the node itself and its type. If the type is IndexedFaceSet2D, then the animation stream decoder knows that it must pass the encoded data to the 2Dmesh decoder, which in turn will update the appropriate fields of the IndexedFaceSet2D node. Texture mapping onto the IndexedFaceSet2D is similar to that in VRML and is explained in the Systems part of the standard.

2. Applications of the 2D Mesh Object

• 2D augmented reality: Merging virtual (computer generated) images with real video objects to create enhanced display information. The computer-generated images must remain in perfect registration with the real video objects, which can be achieved by 2D mesh tracking of video objects. 2D augmented reality application is demonstrated in Figure 25.
• Editing texture of video objects: Replacing a natural video object in a clip by another video object. The replacement video object may be extracted from another natural video clip or may be transfigured from a still image object using the motion information of the object to be replaced (hence the need for a temporally continuous motion representation). This is called synthetic-object-transfiguration.
• Spatio-temporal interpolation: Mesh motion modeling provides more robust motion-compensated temporal interpolation (frame rate up-conversion).

1. Conclusions

   MPEG-4 integrates synthetic and natural content in multimedia communications and documents. In particular, two types of synthetic visual objects are defined in version 1: animated faces and animated 2D meshes. MPEG-4 defines a complete set of animation parameters tailored towards animation of the human face. In order to enable animation of a face model over low bitrate communication channels, for point to point as well as multi-point connections, MPEG-4 encodes the facial animation parameters using temporal prediction. Face models can be animated with a data rate of 300 - 2000bits/s. MPEG-4 also defines an application program interface for TTS synthesizer. Using this interface, the synthesizer can be used to provide phonemes and related timing information to the face model. This allows for animated talking heads driven just by one text stream.

   2D meshes provide means to represent and/or animate generic 2D objects. MPEG-4 version-1 accommodates both uniform and Delaunay 2-D meshes. 2-D meshes with arbitrary topology can be realized as a special case of 3D generic meshes (which will become available in MPEG-4 version 2) and can be animated using the BIFS-Anim elementary stream. Experimental results indicate that coding efficiency of the 2D dynamic mesh representation (for uniform and Delaunay meshes) described in this paper is significantly better when compared to that of 2D generic mesh animation using BIFS-Anim.

   It is important to note that both face animation and 2D mesh animation may be used as representations of real video objects for highly efficient compression (model-based coding) or to generate completely synthetic video objects (virtual or augmented reality). Of course, the model-based coding application requires powerful video object analysis tools to estimate the animation parameters that would imitate real video objects.

   Acknowledgements:

   The authors would like to thank Dr. Peter van Beek for his contributions and Prof. Yao Wang and Prof. F. Pereira for their review of the manuscript.

2. References

   [1] S. Morishima and H. Harashima, "A Media Conversion from Speech to Facial Image for Intelligent Man-Machine Interface", IEEE Jou. Selected Areas in Communications, vol. 9, no. 4, pp. 594-600, May 1991.

   [2] Kalra P., Mangili A, Magnenat-Thalmann N, Thalmann D. "Simulation of Facial Muscle Actions Based on Rational Free Form Deformations", Proc. Eurographics 92, pp. 59-69, 1992.

   [3] R. Sproat and J. Olive, "An Approach To Text-to-speech Synthesis", In W.B. Kleijn & K.K. Paliwal (Eds.) Speech Coding and Synthesis, Elsevier Science, 1995.

   [4] F. I. Parke, "Parameterized Models for Facial Animation", IEEE Computer Graphics and Applications, vol. 2, pp. 61-68, Nov. 1982.

   [5] M. M. Cohen and D. W. Massaro, Modeling Coarticulation in Synthetic Visual Speech, In M. Thalmann & D. Thalmann (Eds.) Computer Animation '93, Tokyo: Springer-Verlag.

   [6] K. Waters and T. Levergood, "An automatic lip-synchronization algorithm for synthetic faces", Proc. of the Multimedia Conference, pages 149-156, San Francisco, California, September 1994. ACM

   [7] J. Ostermann and E. Haratsch, "An animation definition interface: Rapid design of MPEG-4 compliant animated faces and bodies", International Workshop on synthetic - natural hybrid coding and three dimensional imaging, pp. 216-219, Rhodes, Greece, September 5-9, 1997.

   [8] C. Bregler, M. Covell, and M. Slaney, "Video Rewrite: Driving Visual Speech with Audio", Proc. ACM SIGGRAPH 97, in Computer Graphics Proceedings, Annual Conference Series, 1997.

   [9] D. Terzopolous and K. Waters, "Physically-based facial modeling, analysis and animation", Jou. of Visualization and Computer Animation, vol. 1, pp. 73-80, 1990.

   [10] K. Waters, "A muscle model of animating three dimensional facial expression", Computer Graphics, Vol. 22, No. 4, pp. 17-24, 1987.

   [11] J. Hartman and J. Wernecke, The VRML handbook, Addison Wesley, 1996.

   [12] ISO/IEC 14772-1: 1997, Information Technology – Computer graphics and image processing – The Virtual Reality Modeling Language – Part 1: Functional specification and UTF-8 encoding.

   [13] ISO/IEC IS 14496-1 Systems, 1999.

   [14] ISO/IEC IS 14496-2 Visual, 1999.

   [15] ISO/IEC IS 14496-3 Audio, 1999.

   [16] L. Chen, J. Ostermann, and T. Huang, ``Adaptation of a generic 3D human face model to 3D range data,'' First IEEE Workshop on Multimedia Signal Processing, Wang and et al (Ed.), IEEE, Princeton, NJ, June 1997, pp. 274-279.

   [17] M. Escher and N. M. Thalmann, "Automatic 3D cloning and real-time animation of a human face, Proc. Computer Animation ’97, Geneva, 1997.

   [18] S. Morishima, "Modeling of facial expression and emotion for human communication system", Display, Vol. 17, pp 15-25, 1996.

   [19] P. Ekman and W.V. Friesen: Manual for the facial action coding system, Consulting Psychologist Press, Inc. Palo Alto, CA, 1978.

   [20] S. Murakami and H. Tadokoro, "Generation of facial expressions based on time functions", Proceedings of IWSNHC3DI, Rhodes, September 97, pp. 212-215.

   [21] Gabriel Abrantes and Fernando Pereira, "MPEG-4 Facial Animation Technology: Survey, Implementation and Results", IEEE CSVT vol. 9, no. 2, pp. 290-305, 1999.

   [22] J. Ostermann and M. Beutnagel, A. Fischer, Y. Wang, "Integration of talking heads and text-to-speech synthesizers for visual TTS", ICSLP 99, Australia, December 99.

   [23] J. Ostermann, "Animation of synthetic faces in MPEG-4", Computer Animation 98,.Philadelphia, June pp. 49-55, 1998.

   [24] F. Lavagetto and R. Pockaj, "The facial animation engine: Toward a high-level interface for the design of MPEG-4 compliant animated faces", IEEE CSVT vol. 9, no. 2, pp. 277-289, 1999.

   [25] H. Tao, H.H. Chen, W. Wu, T.S. Huang, "Compression of facial animation parameters for transmission of talking heads", IEEE CSVT vol. 9, no. 2, pp. 264-276, 1999.

   [26] I. Pandzic, J. Ostermann, and D. Millen, "User Evaluation: Synthetic Talking faces for Interactive Services", accepted for publication in The Visual Computer, Special Issue on Real-time Virtual Worlds, 1999.

   [27] A. M. Tekalp, Digital Video Processing, Prentice Hall, 1995.

   [28] M. de Berg, M. van Kreveld, M. Overmars, and O. Scharzkopf, Computational Geometry - Algorithms and Applications, Berlin, Germany: Springer, 1997.

   [29] Y. Wang and J. Ostermann, "Evaluation of mesh-based motion estimation in H.263 like coders", IEEE Trans. on Circuits and Systems in Video Technology, pp. 243 – 252, 1998.

   [30] Y. Nakaya and H. Harashima, "Motion compensation based on spatial transformations," IEEE Trans. Circ. and Syst for Video Technology, vol. 4, no. 3, pp. 339-356, June 1994.

   [31] Y. Altunbasak and A. M. Tekalp, " Closed-form connectivity preserving solutions for motion compensation using 2-D meshes," IEEE Trans. on Image Proc., vol. 6, no. 9, pp. 1255-1269, Sept. 1997.

   [32] Y. Wang and O. Lee, "Active mesh- A feature seeking and tracking image sequence representation scheme," IEEE Trans. Image Proc., vol. 3, no. 5, pp. 610-624, Sept. 1994.

   [33] Y. Altunbasak and A. M. Tekalp, "Occlusion-adaptive, content-based mesh design and forward tracking," IEEE Trans. on Image Proc., vol. 6, no. 9, pp. 1270-1280, Sept. 1997.

   [34] C. Toklu, A. T. Erdem, M. I. Sezan, and A. M. Tekalp, "Tracking motion and intensity variations using ierarchical 2-D mesh modeling," Graphical Models and Image Processing, vol. 58, no. 6, pp. 553-573, Nov. 1996.

   [35] A. M. Tekalp, P. J.L. van Beek, C. Toklu, and B. Gunsel, "Two-dimensional mesh-based visual object representation for interactive synthetic/natural digital video," Proc. of the IEEE, vol. 86, no. 6, pp. 1029-1051, June 1998.

   [36] P. J.L. van Beek, A. M. Tekalp, N. Zhuang, I. Celasun, and M. Xia, "Hierarchical 2D mesh representation, tracking, and compression for object-based video," IEEE Trans. Circ. and Syst. for Video Tech., vol. 9, no.2, pp. 353-369, March 1999.

   [37] P. E. Eren, N. Zhuang, Y. Fu, and A. M. Tekalp, "Interactive object-based analysis and manipulation of digital video," IEEE Workshop on Multimedia Signal Processing, Redondo Beach, CA, Dec. 1998.

    

   Murat Tekalp

   A. Murat Tekalp received B.S. degree in Electrical Engineering, and B.S. degree in Mathematics from Bogazici University, Istanbul, Turkey in 1980, with the highest honors, and M.S. and Ph.D. degrees in Electrical, Computer and Systems Engineering from Rensselaer Polytechnic Institute (RPI), Troy, New York, in 1982 and 1984, respectively. From December 1984 to August 1987, he was a research scientist, and then a senior research scientist at Eastman Kodak Company, Rochester, New York. He joined the Electrical Engineering Department at the University of Rochester, Rochester, New York, as an Assistant Professor in September 1987, where he is currently a Professor. His current research interests are in the area of digital image and video processing, including object-based video representations, motion tracking, image/video segmentation, video filtering and restoration, image/video compression, and multimedia content description.

   Prof. Tekalp is a senior member of IEEE, and a member of Sigma Xi. He received the NSF Research Initiation Award in 1988, Fulbright Scholar Award in 1999, and named as Distinguished Lecturer by IEEE Signal Processing Society in 1998. He is listed in Marquis Who'sWho in America Science and Engineering, 4th and 5th editions, and Who'sWho in the World, 17th Edition. He has chaired the IEEE Signal Processing Society Technical Committee on Image and Multidimensional Signal Processing (Jan. 1996 - Dec. 1997). He has served as an Associate Editor for the IEEE Trans. on Signal Processing (1990-1992), and IEEE Trans. on Image Processing (1994-1996). He has also been guest editor for recent special issues of Proceedings of the IEEE (on Multimedia Signal Processing, May/June 1998), IEEE Transactions on Image Processing (on Image and Video Processing for Digital Libraries, to appear), Signal Processing: Image Communications (on Real-Time Video over the Internet, September 1999). At present, he is on the editorial boards of Academic Journals Graphical Models and Image Processing, and Visual Communication and Image Representation, and the EURASIP journal on Signal Processing: Image Communication. He is also an Associate Editor for the Kluwer Journal Multidimensional Systems and Signal Processing. He was appointed as the Technical Program Chair for the 1991 IEEE Signal Processing Society Workshop on Image and Multidimensional Signal Processing, the Special Sessions Chair for the 1995 IEEE International Conference on Image Processing, and the Technical Program Co-Chair for IEEE ICASSP 2000 (to be held in Istanbul, Turkey). He is the founder and first Chairman of the Rochester Chapter of the IEEE Signal Processing Society. He was elected as the Chair of the Rochester Section of IEEE in 1994-1995. Dr. Tekalp is the author of the Prentice Hall book Digital Video Processing (1995).

    

   Jörn Ostermann

   Jörn Ostermann studied Electrical Engineering and Communications Engineering at the University of Hannover and Imperial College London, respectively. He received Dipl.-Ing. and Dr.-Ing. from the University of Hannover in 1988 and 1994, respectively.

   From 1988 till 1994, he worked as a Research Assistant at the Institut für Theoretische Nachrichtentechnik conducting research in low bit-rate and object-based analysis-synthesis video coding. In 1994 and 1995 he worked in the Visual Communications Research Department at AT&T Bell Labs. He has been working with Image Processing and Technology Research within AT&T Labs - Research since 1996.

   From 1993 to 1994, he chaired the European COST 211 sim group coordinating research in low bitrate video coding. Within MPEG-4, he organized the evaluation of video tools to start defining the standard. Currently, he chairs the Adhoc Group on Coding of Arbitrarily-shaped Objects in MPEG-4 Video. Jörn was a scholar of the German National Foundation.

   In 1998, he received the AT&T Standards Recognition Award and the ISO award. He is a member of IEEE, the IEEE Technical Committee on Multimedia Signal Processing, and the IEEE CAS Visual Signal Processing and Communications (VSPC) Technical Committee.

   His current research interests are video coding, computer vision, 3D modeling, face animation, coarticulation of acoustic and visual speech, computer-human interfaces, and speech synthesis.

    

    

    

3. Annex