Method of streaming a 3-d wireframe animation

Description of equivalent WO 2004019619 A2

SYSTEM AND METHOD OF STREAMING 3-D WIREFRAME ANIMATIONS

PRIORITY CLAIM

[0001] The present application claims priority to U.S. Provisional Patent Application No. 60/404,410, filed August 20, 2002, the contents of which are incorporated herein by reference.

RELATED APPLICATION [0002] Non-Provisional Application, entitled "Coding of Animated 3-D Wireframe Models For Internet Streaming Applications: Methods, Systems and Program Products", Serial Number 10/198129, filed July 19, 2002, assigned to the same assignee as that of the present applications and fully incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

[0003] The present invention relates to streaming data and more specifically relates to a system and method of streaming 3-D wireframe animations.

2. Introduction

[0004] The Internet has rapidly evolved during the past few years from a low-bandwidth, text- only collaboration medium, to a rich, interactive, real-time, audio-visual virtual world. It involves many users, environments and applications, where 3-D animations constitute a driving force. Animated 3-D models enable intuitive and realistic interaction with displayed objects and allow for effects that cannot be achieved with conventional audio-visual animations. Consequently, the current challenge is to integrate animated 3-D geometry as a new data stream in the existing evolving infrastructure of the Internet, in a way that both enhances the existing networked environment and respects its limited resources. Although static 3-D mesh geometry compression has been actively researched in the past decade, very little research has been conducted in compressing dynamic 3-D geometry, which is an extension of static 3-D meshes to the temporal domain. [0005] The most prevalent representations for 3-D static models are polygonal or triangle meshes. These representations allow for approximate models of arbitrary shape and topology within some desired precision or quality. Efficient algorithms and data structures exist to generate, modify, compress, transmit and store such static meshes. Future, non-static, stream types that introduce the time dimension, would require scalable solutions to survive with respect to the network's limited resources (bandwidth) and characteristics (channel errors). [0006] The problem of 3-D wireframe animation streaming addressed herein can be stated as follows: Assume (i) a time-dependent 3-D mesh has been scalably compressed in a sequence of wireframe animation frames, (ii) the available transmission rate R is known (or determined with respect to the corresponding TCP-friendly rate), (iii) the channel error characteristics are known, and (iv) a fraction C of the available transmission rate (C < R) can be reserved for channel coding. Then, the issue is to identify the optimal number of bits to be allocated to each level of importance (layer) in the animation scene that maximizes the perceived quality of the time-dependent mesh at the receiver.

[0007] Most animation coding approaches use objective metrics to achieve a hierarchical coding of static 3-D meshes. What is needed is an animation approach that utilizes a subjective quantity, such as visual smoothness, to provide an improved appearance of animation. Described herein is a 3-D wireframe animation codec and its bitstream content, along with the associated forward error correction (FEC) codes. The visual distortion metric as well as the unequal error protection (UEP) method and receiver-based concealment method are further explained.

SUMMARY OF THE INVENTION [0008] The present invention focuses on source and channel coding techniques for error resilient time-dependent 3-D mesh streaming over the Internet that respects network bandwidth and considers the bursty loss nature of the channel. [0009] An exemplary embodiment of the invention is a method of streaming data comprising computing a visual smoothness value for each node in a wireframe mesh and layering data associated with the wireframe mesh into a plurality of layers such that an average visual smoothness. value associated with each layer reflects the respective layer's importance in an animation sequence. Other embodiments of the invention may include a bitstream generated according to a process similar to the above method and an apparatus of generating and transmitting a bitstream or receiving a bitstream.

[0010] Additional features and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The features and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims. These and other features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth herein.

BRIEF DESCRIPTION OF THE DRAWINGS [0011] In order to describe the manner in which the above-recited and other advantages and features of the invention can be obtained, a more particular description of the invention briefly described above will be rendered by reference to specific embodiments thereof which are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments of the invention and are not therefore to be considered to be limiting of its scope, the invention will be described and explained with additional specificity and detail through the use of the accompanying drawings in which: [0012] Figure 1A is a block diagram of a 3-D Animation codec; [0013] Figure IB is a block diagram of a decoder;

[0014] Figure 2 is a comparative plot of distortion metrics including PSNR, Hausdorff Distance and Visual Smoothness; [0015] Figure 3A represents a flowchart of method of error resilient wireframe streaming;

[0016] Figure 3B illustrates a flowchart according to an aspect of the invention;

[0017] Figure 4 is a comparative plot of three error concealment methods for sequence for wireframe animation TELLY;

[0018] Figure 5 is a comparative plot of Visual smoothness (VS) transmitted and decoded frames of 3 layers of the wireframe animation TELLY; and

[0019] Figure 6 is a comparative plot of Visual Smoothness between transmitted and decoded frames of 2 layers of wireframe animation BOUNCEBALL.

DETAILED DESCRIPTION OF THE INVENTION [0020] Much research has been undertaken to study streaming video across computer networks in general and over the Internet in particular. Relatively little has been undertaken in the field of streaming 3-D wireframe animation. Although both processes may have some similarities, the two are significantly different. Different data passes across the network, so loss affects signal reconstruction differently. The perceptual effects of such loss have been poorly addressed in the art. Much of the work in this area reHed on objective measures such as PSNR in lieu of those that take subject effects into account.

[0021] The present invention brings together concepts from a number of fields to address the problem of how to achieve optimal resilience to errors in terms of the perceptual effect at the receiver. In this regard, the invention relates to a subjective quality of an animation, for example, the mesh surface smoothness. To achieve an improved coding scheme taking subjective factors into account, an aspect of the invention comprises partitioning the animation stream into a number of layers and applying Reed-Solomon (RS) forward error correction (FEC) codes to each layer independently and in such a way as to maintain the same overall bitrate whilst minimizing the perceptual effects of error, as measured by a distortion metric related to static 3-D mesh compression. Graceful degradation of streamed animations at higher packet loss rates than other approaches can be achieved by the unequal error protection (UEP) approach combined with error concealment (EC) and an efficient packetization scheme.

[0022] The present disclosure first provides an overview of the 3D-Animation codec that introduces the related notation, followed by an overview of the error correcting RS codes follows together with derivation of the channel model, as well as an exemplary description of

UEP packetization for the encoded bitstream.

[0023] The vertices m of a time-dependent 3-D mesh form the indexed set M,. = {m_jt; j = 1,

2, ..., n}, at time t, where n is the number of vertices in the mesh. Since a vertex has three space components (x:, v, Z_j), and assuming that no connectivity changes occur in time

(constant n), we can represent the indexed set's data at time t by the position matrix M_t, as:

<img file="WO2004019619A2_D0001.tif" />

[0024] The indexed set of vertices are partitioned into intuitively natural partitions, called nodes. The term "node" is used to highlight the correspondence of such nodes with the nodes as defend in VRML. The position matrix corresponding to the i^th node is denoted by N_{i t}. Note that without loss of generality, the vertex matrix can now be expressed as:

for k such nodes. For notational convenience, the terms N_{i t}(i = 1, 2, ..., k) are used both for representing a matrix and to refer to the i^th node as well. The objective of the 3D-Animation compression algorithm is to compress the sequence of matrices M_t that form the synthetic animation, for transmission over a communications channel. Obviously, for free-form animations of a 3-D mesh the coordinates of the mesh may exhibit high variance, which makes the M,. matrices unsuitable for compression. Hence, the signal can be defined as the set of non-zero displacements of all vertices in all nodes at time t:

Di = {da = - m„rj.i = 1_&gt;2, . ^p (p &lt; n) d_it ^ 0} Following this notation, the above can be expressed with a displacement matrix, D„ as:

<img file="WO2004019619A2_D0002.tif" />

or equivalently, using node matrices:

D_t = Fι,s F_2{1 . . . Fι_it\ (])

where F_it the displacement matrix of node i, for 1 such nodes (i= 1, 2, ..., 1). Note that D_t's dimension is reduced to p ≤ n compared to M_t, since D_t does not contain vertices for which the displacement on all axes is zero. Note, too, that 1&lt; k holds, in the event that no vertices in a node get displaced (F_i;t — 0). In 3D-An nation terminology, sparse animations are referred to as those sequences with p &lt; n and 1 &lt; k, whereas if p = n and 1 = k the animation is called dense. It is evident that if an encoder is capable of controlling parameters p and 1, it can generate a layered bitstream (by adjusting parameter 1), where every layer L can be scalable (by adjusting parameter p). The sparsity (or density) of the animation is qualified by the density factor, defined as:

df = _s with I &lt; k and JJ &lt; n. (2) <img file="WO2004019619A2_D0003.tif" /> in the range [0..1], where F is the number of animation frames and k the number of nodes in the reference model. For p → n and l → k, then df — 1, therefore a complete animation. [0025] The concept described and summarized in equation (1) above, is suited to a DPCM coder, as detailed below. The coding process assumes that the initial wireframe model M₀, here termed as the reference model, is already present at the receiver. The reference model can be compressed and streamed with an existing method for static 3-D mesh transmission, along with error protection if it is assumed the transmission is done over the same lossy channel as the time-dependent mesh. Such existing methods can accommodate and interoperate with static mesh transmissions and will not be discussed further here. [0026] In the 3D-Animation codec's context, an I-frame describes changes from the reference model M₀ to the model at the current time instant t. A P-frame describes the changes of a model from the previous time instant t - 1 to the current time instant t. The corresponding position and displacement matrices for I and P frames are denoted respectively by

<img file="WO2004019619A2_D0004.tif" />

[0027] Figure 1A shows an exemplary block diagram 100 of a coding process according to an aspect of the invention. The diagram illustrates a DPCM encoder that takes advantage of the temporal correlation of the displacement of each vertex along every axis in the 3-D space. To encode a P-frame, the decoded set (animation frame or displacement matrix) of the previous

instance is used as the predicted value 108, 106 D_t__x . (Equivalently for encoding an I-frame

the predicted matrix is D_t_ where at t = 0 is the displacement matrix for the reference model.)

Then, the prediction error E_t, i.e. the difference between the current displacement matrix and

the predicted one 106 is computed 102 and quantized 104\E_t ). Finally, the quantized samples

are entropy coded (C,) using an adaptive arithmetic coding algorithm 110 to handle the unknown data statistics. This predictive scheme prevents quantization error accumulation. [0028] A DPCM decoder 120 is shown in Figure IB. The decoder 120 first decodes

arithmetically the received samples 122 (C,) and computes the decoded samples 124, 126 (A ).

The quantization range of each node is determined by their bounding box. The quantization step size can be assumed to be the same for all nodes, or can vary in order to shape the encoded bitstream rate. Allowing different quantization step sizes for different nodes may result in artifacts such as mesh cracks, especially in the boundaries between nodes. [0029] The discloser mentions above that D_t's dimension is reduced to p &lt; n compared to M_j, since it does not contain vertices for which the displacement on all axes is zero. This property provides an advantage against MPEG-4's BIFS- Animation, which does not allow for reduced animation frames. For sparse D_t matrices it may also be the case that a whole node is not animated thus allowing great animation flexibility and generating a scalable bitstream. Furthermore, in the case where F_;&gt;t = 0, Vi e [l.i], the displacement matrix D_t is zero, leading

to an 'empty' frame. This property resembles the silence period inherent in speech audio streams and can be exploited in the application layer of RTP-based receivers to absorb network jitter. Inter-stream synchronization can also be achieved, which is paramount for many applications (e.g. lip synchronization of a 3-D animated virtual salesman with packet speech).

[0030] Next is described a channel model and error correction codes. The idea of Forward Error Correction (FEC) is to transmit additional redundant packets which can be used at the receiver to reconstruct lost packets. In the FEC process according to a preferred embodiment of the present invention, Reed- Solomon (RS) codes are used across packets. RS codes are the only non-trivial maximum distance separable codes known, hence they are suitable for protection against packet losses over bursty loss channels. An RS(n, k) code of length n and dimension k is defined over the Galois Field GF (2^q) and encodes k q-bit information symbols into a codeword of n such symbols, i.e. n &lt; 2^q - 1. A sender needs to store copies of k information packets in order to calculate n - k redundancy packets. The resulting n packets are stacked in a block of packet (BOP) structure. This BOP structure is known in the art and thus not explained further herein. To maintain a constant total channel data rate, the source rate is reduced by the fraction k/n, called the code rate, resulting in an initially reduced animation quality. A receiver can begin decoding as soon as it receives any k correct symbols, or packets of a BOP.

[0031] In reality, the underlying bursty loss process of the Internet is quite complex, but it can be closely approximated by a 2-state Markov model. The two states are state G (good), where packets are timely and correctly received, and B (bad), where packets are either lost or delayed to the point that they that can be considered lost. The state transition probabilities p_GB and p_BG fully describe the model, but since they are not sufficiently intuitive, the model can be expressed using the average loss probability P_B, and the average burst length ,_B, as:

P_B = Pτ(B) = ^ (3)

<img file="WO2004019619A2_D0005.tif" />

[0032] For the selection of the RS code parameters the probability needs to be known that a BOP cannot be reconstructed by the erasure decoder as a function of the channel and the RS code parameters. For an RS(n, k) code, this is the probability that more than n - k packets are lost within a BOP, and it is called the block error rate, P_BER. Let P (m, n) be the probability of m lost packets within a block of n packets, also called the block error density function. Then, the calculation is: n

PBRR = <img file="WO2004019619A2_D0006.tif" />

[0033] The average loss probability P_B and the average loss burst Lg corresponding to the 2- state Markov model described above, relate to block error density function P (m, n). The exact nature of their relationship has been extensively studied and derived in the literature. Here we adapt the derivation for bit error channels to a packet loss channel. [0034] The Markov model as described before is a renewal model, i.e. a loss event resets the loss process. Such a model is determined by the distribution of error-free intervals (gaps). If there occurs an event of gap length v such that v - 1 packets are received between two lost packets, then the gap density function g(v) gives the probability of a gap length v, i.e. g(v) =

Pr(0^v-1 1 1) . The gap distribution function G(v) gives the probability of a gap length greater

than v -1, i.e. G(v) = Pr(0^v~ | 1) . In state B of our model all packets are lost, while in state G all packets are received, yielding: 1 - PBG, ^βiy) = pøc(l - pa ■ f \v'~~²2p, aB v &gt; l

<img file="WO2004019619A2_D0007.tif" />

[0035] Let R(m, n) be the probability of m - 1 packet losses within the next n - 1 packets following a lost packet. This probability can be calculated from the recurrence:

<img file="WO2004019619A2_D0008.tif" />

Then, the block error density function P (m, n) or probability of m lost packets within a block of n packets is given by:

rra = 0

P[m._tn) {1 2-w=α

PBG(v)R(tn_i n μ + i), 1 1 &lt; m &lt; n

where P_B is the average error probability.

[0036] From Eq. 5, it is noted that P (m, n) determines the performance of the FEC scheme, and can be expressed as a function of P_B, L^ using Eq. 3 and 4. As explained below, the expression of P (m, n) can be used in a RS(m, n) FEC scheme for optimized source/channel rate allocation that rninimizes the visual distortion.

[0037] Next is described a bitstream format and packetization process. The output bitstream of the 3D-Animation codec needs to be appropriately packetized for streaming with an application-level transport protocol, e.g. RTP. This process for a single layer bit- stream is known and its main features are summarized by the following three concepts: [0038] (1) In order to describe which nodes of the model are to be animated the animation masks, NodeMask and VertexMasks are defined in a similar way to BIFS-Anim. The NodeMask is essentially a bit-mask where each bit, if set, denotes that the corresponding node in the Node Table will be animated. The Node Table (an ordered Ust of all nodes in the scene) is either known a priori at the receiver since the reference wireframe model exists there already, or is downloaded by other means. In a similar way, the VertexMasks are defined, one per axis, for the vertices to be animated.

[0039] (2) In its simplest form, one frame (which represents one Application Data Unit (ADU)), is contained in one RTP packet. In this sense, the 3D-Animation codec's output bit- stream is 'naturally packetizable' according to the known Application Level Framing (ALF) principle. An RTP packet payload format is considered starting with the NodeMask and VertexMasks, followed by the encoded samples along each axis.

[0040] (3) The M bit in the RTP header must be set for the first of a series of 'empty' frames, which (if they exist) can be grouped together.

[0041] This simple format suffices for light animations with a modest number of vertices. However, sequences with high scene complexity or high-resolution meshes may generate a large number of coded data after compression, resulting in frames that potentially exceed the path MTU. In such cases, raw packetization in a single layer would require the definition of fragmentation rules for the RTP payload, which may not always be straightforward in the ALF sense. Furthermore, frames directly packetized in RTP as described above generate a variable bitrate stream due to their varying lengths.

[0042] A more efficient packetization scheme is sought that satisfies the requirements set out above: (a) to accommodate layered bitstreams, and (b) to produce a constant bitrate stream. This efficiency can be achieved by appropriately adapting the block structure known as Block- Of-Packets (BOP). In this method, encoded frames of a single layer are placed sequentially in line order of an n-line by S_P -column grid structure and then RS codes are generated vertically across the grid. For data frames protected by an RS (n, k) erasure code, error resilience information is appended so that the length of the grid is n for k frames of source data. This method is most appropriate for packet networks with burst packet errors, and can be fully described by the sequence frame rate FR, the packet size S_P, the data frame rate in a BOP F_BOP

<img file="WO2004019619A2_D0009.tif" /> [0043] Intuitively, for a BOP consisting of F_BOP data frames, with S_p bytes long packets, at FR frame rate, the total source and channel bitrate R is given by:

n - FR ^« Sp , ..,

R = £_f (&amp;)

■F^'BOP

[0044] This equation serves as a guide to the design of efficient packetization schemes by appropriately balancing the parameters F_B0P, n and S_P. It also encompasses the trade-off between delay and resilience. For a layered bitstream, a design is needed for one BOP structure per layer. By varying the parameters in Eq. 6, different RS code rates can be allocated to each layer, thus providing unequal level of error protection to each layer. The way these parameters are adjusted in practice for the application of 3-D animation streaming, considering a measure of visual error, is explained next.

[0045] In order to measure the visual loss resulting from a non-perfect reconstruction of the animated mesh at the receiver, a metric is required that is able to capture the visual difference

between the original mesh M_t at time t and its decoded equivalent M_t . The simplest measure

is the RMS geometric distance between corresponding vertices. Alternatively, the Hausdorff Distance has been commonly used as an error metric. The Hausdorff distance is defined in the present case as the maximum minimum distance between the vertices of two sets, M_j and

M_t in such a way that every point M,lies within the distance H (M_t , M_t ) of every point in- M,

and vice versa. This can be expressed as:

<img file="WO2004019619A2_D0010.tif" />

where h(M,. , M_t ) =

max mm. \n — m_ft J, <img file="WO2004019619A2_D0011.tif" /> and I) • || is the Euclidean distance between the two vertices, m_t and m_t . Many other

distortion metrics can be derived by equivalence to natural video coding, such SNR and PSNR, but they are tailored to the statistical properties of the specific signal they encode, failing to give a uniform measure of user perceived distortion across a number of signals and encoding methods over different media. Moreover, especially for 3-D meshes, all these metrics give only objective indications of geometric closeness, or signal to noise ratios, and they fail to capture the more subtle visual properties the human eye appreciates, such as surface smoothness.

[0046] Figure 2 illustrates a comparative plot 200 of distortion metrics: PSNR, Hausdorff Distance, and Visual Smoothness for 150 frames of the animated sequence BOUNCEBALL with I-frame frequency at 8 Hz. The two upper plots (PSNR-Hausdorff) show the expected correlation between the corresponding metrics of geometric distance and Hausdorff Distance (eq. 7) they represent. The two lower plots indicate that the visual distortion (eq. 8) might be low in cases where the geometric distance is high and vice-versa.

[0047] One attempt that was made in the direction of using surface smoothness was reported by Kami and Gotsman as being undertaken whilst evaluating their spectral compression algorithm for 3-D mesh geometries. See, Zachi Kami and Craig Gotsman, "Spectral compression for mesh geometry," in Siggraph 2000, Computer Graphics Proceedings. Kurt Akeley, Ed. 2000, pp. 279 - 286, ACM Press/ACM SIGGRAPH/Addison Wesley Longman, incorporated herein by reference. In this, the suggested 3-D mesh distortion metric normalizes the objective error computed as the Euclidean Distance between two vertices, by each vertex's distance to its adjacent vertices. This type of error metric captures the surface smoothness of the 3-D mesh. This may be achieved by a Laplacian operator, which takes into account both topology and geometry. The value of this geometric Laplacian at vertex v_; is:

<img file="WO2004019619A2_D0012.tif" /> where n(i) is the set of indices of the neighbors of vertex i, and l_;i is the geometric distance between vertices i and j. Hence, the new metric is defined as the average of the norm of the geometric distance between meshes and the norm of the Laplacian difference (m_t ήι_t are the

vertex sets of meshes M_t M _t respectively, and n the set size of M_t M _t ):

\\M_t ~M_t\\ = -(| » - + \\G {m_t) - OL(rn._t)\\) (3)

[0048] This metric in Eq. 8 is preferably used in the present invention, and will be referred to hereafter as the Visual Smoothness metric (VS). Other equations that also relate to the visual smoothness of the mesh may also be used.

[0049] The VS metric requires connectivity information such as the adjacent vertices of every vertex m_t. For the case of the 3D- Animation codec, where it is assumed that no connectivity changes during the animation, the vertex adjacencies can be precomputed.

[0050] The BOP structure described above is suitable for the design of an efficient packetization scheme that employs redundancy information based on RS erasure codes. The relation of its design parameters was also shown in Eq. 6. This equation, though, does not reflect any information about layering. An exemplary layering design approach is described next, followed by the proposed error resilient method for 3-D wireframe streaming.

[0051] The layering is performed in a way that the average VS value of each layer reflects its importance in the animation sequence. To achieve this, the VS from Eq. 8 is computed for every node in the mesh independently and the nodes are ordered according to their average VS in the sequence. A node, or group of nodes, with the highest average VS forms the first and most important layer visually, L₀. This is the layer that should be more resilient to packet errors than other layers. Subsequent importance layers L_α, ..., L_M are created by correspondingly subsequent nodes, or group of nodes, in the VS order.

[0052] If a 3-D mesh has more nodes than the desirable number of layers, then the number of nodes to be grouped in the same layer is a design choice, and dictates the output bitrate of the layer. For meshes with only a few nodes but large number of vertices per node, node partitioning might be desirable. The partitioning would restructure the 3-D mesh's vertices in a new mesh with more nodes than originally. This process will affect connectivity, but not the overall rendered model. Mesh partitioning into nodes, if it is possible, should not be arbitrary, but should rather reflect the natural objects these new nodes will represent in the 3-D scene and their corresponding motion. If partitioning is not possible in the above sense, one could partition the mesh in arbitrary sized sub-meshes (nodes) that will be allocated to the same layer. Mesh partitioning may require complex pre-processing steps that would be understood by one of skill in the art. Recall, however, that the 3D-Animation codec assumes static connectivity.

[0053] It is common practice in "natural video" to build layers with a cumulative effect. That is, layer L data add detail to the data of layer Lμ and improve the overall quality of video. But, one can decode only up to layer L_)Λ and forget about the refinement layers. This approach may be taken in an adaptive streaming scenario, where a sender may choose to send only j-1 layers during congested network conditions, and j or more layers when the network conditions improve, i.e., more bandwidth becomes available.

[0054] The nature of 3-D animation layers disclosed herein is not always cumulative in the same sense. Decoding layer L (which has been built with appropriate node grouping or node partitioning) does not necessarily only refine the quality of data contained in previous layers L o— i, but adds animation details to the animated model by, for example, adding animation to more vertices in the model.

[0055] As an example, consider the sequence TELLY (discussed more fully below), which is a head-and- shoulders talking avatar. TELLY always faces the camera (static camera). Since the camera does not move, it is a waste of bandwidth to animate the back side of the hair. However, one can easily detect the visible and invisible parts (set of vertices) of the hair and with appropriate partitioning of node "hair" to allocate the visible part to layer _Λ and the invisible part to layer L₍. In the case of a static camera (and where no interactivity is allowed) layer L, is not transmitted. Thus when a user views the wireframe mesh or animation in a static mode, only the visible portions of the animation can be seen since the animation does not rotate or move. In the case where the user should be able to examine the animation by rotating or zooming in on the avatar (or other model), or look at the back side of it, layer L, is sent. In this case, the user views the animation in an interactive mode that enables the user to view portions of the animation that were invisible in the static mode, due to the lack of motion of the animation. But, layer L does not refine the animation of the visible node of the hair in layer L_j . It contains additional animation data for the invisible vertices. This provides an example result of the partitioning method.

[0056] Further, the "interactive mode" does not necessarily require user interaction with the animation. The interactive mode refers to any viewing mode wherein the animation can move or rotate to expose a portion of the animation previously hidden. Thus, in some cases where the viewer is simply looking at the animation, the animation may move and rotate in a more human or natural way while speaking. In this case, the h_] layer or other invisible layers may be sent to provide the additional animation data to complete the viewing experience. In this regard, the static or interactive mode may depend on bandwidth available. I.e., if enough bandwidth is available to transmit both visible and invisible layers of the animation, then the animation can be viewed in an interactive mode instead of a static mode. In another aspect of the invention, the user may select the static or interactive mode and thus control what layers are transmitted.

[0057] Figure 3A illustrates an example set of steps according to an aspect of the invention. The method comprises partitioning the 3-D wireframe mesh (302), computing the VS value for each node in the mesh (304) and layering data associated with the wireframe mesh into a plurality of layers such that an average VS value associated with each layer reflects the respective layer's importance in an animation sequence (306). The same overall bitrate is maintained when transmitting the plurality of layers by applying the error correction code to each layer where the error correction code is unequal in the layer according to the layer's importance (308).

[0058] The terms "partition" as used herein can mean a preprocessing step such as partitioning the mesh into arbitrary or non-arbitrary sub-meshes that will be allocated to the same layer. Further, the term may also have other applications, such as the process of generating the various layers comprising one or more nodes.

[0059] Figure 3B illustrates a flowchart of another aspect of the invention. The method comprises allocating more redundancy to a layer of the plurality of layers that exhibits the greatest visual distortion (320). This may be, for example, a layer comprising visually coarse information. Next, the redundancy is gradually reduced on layers having less contribution to visual smoothness (322). Interpolation-based concealment is applied to each layer at the receiver where an irrecoverable loss of packets occurs only within the respective layer (324) from the standpoint of the receiver. As packets belonging to a particular layer travel through the communications network, they may take different paths from the sender to the receiver, thus suffering variable delays and losses. When the receiver sees an overall packet loss rate, the receiver will try to reduce the loss rate by using the redundant information (FEC) provided separately in each layer. The amount of FEC may not be enough to recover all missing packets (residual packets). The interpolation-based concealment can be applied to each layer independently to reduce the distortion introduced by residual packet loss. In general, steps 320 and 322 are performed on the coding/ transmitter end and step 324 is performed at the receiver over a communications network, such as a peer-to-peer network. [0060] The expected distortion of the animation at the receiver at time t is the sum of the product quantities P_jt^• D_jt, where j is the layer index, D_jt is the visual distortion incurred by missing information in layer j at time t, and P_jt is the probability of having an irrecoverable packet loss in layer j. By the way we constructed the layers, the probabilities P_jt are independent, and a burst packet loss in a layer contributes its own visual distortion D_jt in the decoded sequence. Formally, the expected visual smoothness VS^ of an animation at the decoder at time t can be expressed as: -X

where L is the number of layers. In the equation above, P_jt is the block error rate P_BER as given by Eq. 5, or the probability of losing more than n - k packets in layer j. Using the block error density function P (m, n), the following is derived: n ^p3* = <img file="WO2004019619A2_D0013.tif" />

From Eqs. 9and 10, VS_(t) can be described as:

<img file="WO2004019619A2_D0014.tif" /> [0061] Equation 11 estimates in a statistical sense the expected visual smoothness experienced per frame at the decoder. The objective is to minimize this distortion with respect to the values of k_jt's in Eq. 11. From the way the bitstream is split into layers it is expected that the optimization process allocates more redundancy to the layer that exhibits the greatest visual distortion (coarse layer), and gradually reduces the redundancy rate on layers with finest contribution to the overall smoothness. There are L values of k_t that need to be calculated at

every time t, that follow the conditions 0 ≤ k_t ≤ n and ^jjT (n - k_Jt ) = R_c / q where R,- the

redundancy bits, and q is the symbol size. The above problem formulation yields a non-linear constraint optimization problem that can be solved numerically.

[0062] The anticipated behavior of the model for P_B = 0 is to produce equal values for k_t's, whereas in high P_B's unequally varying k_jt's would be obtained. Note that for the calculation of smoothness distortions in Eq. 11, it is assumed that no error concealment takes place at the receiver. [0063] It has been shown that techniques based on vertex linear interpolation are a sufficient and efficient method of error concealment for 3D-Animation frames. This relies on the 'locality of reference principle', according to which high- frame rate animations are unlikely to exhibit vertex trajectories other than linear or piece-wise linear. If higher complexity can be accommodated, higher order interpolation can be employed by using information from the neighboring frames. Some known interpolation and other concealment methods are generic in that they can be used by any other decoder.

[0064] Figure 4 is a graph 400 illustrating the relative performances of three error concealment methods adapted to the experimental parameters of this work, namely P_B = [0..30] and L^ = 4. It is evident that linear interpolation outperforms Frame Repetition or Motion Vector-based methods. The plot shows average values for 8 iterations with different loss patterns. It is clear on the plot (as seen by the error bars) that the interpolation concealment method exhibits very low variance, verifying the locality of reference principle (the average loss burst length Lg = 4 is much lower than the sequence frame rate of 30 Hz.) Therefore, the present invention preferably uses interpolation-based error concealment at the receiver in the case where the channel decoder receives less than n - k_jt BOP packets. In fact, the k_jt's that provide a solution to the optimization problem, will also give minimum distortion if combined with concealment techniques. The expected distortion in such cases will be lower than the distortion without error concealment.

[0065] The following explains the experimental procedure and how to tune the values and the optimization process for a real-world case of 3-D wireframe animation, along with discussion of experimental results using the present invention.

[0066] The following experiments demonstrate through simulation the efficiency of the proposed Unequal Error Protection (UEP) scheme combined with Error Concealment (EC) for streaming 3-D wireframe animations. In particular, using UEP with EC is compared to simple UEP, to Equal Error Protection (EEP) and to No Protection (NP). The comparison is based on the Visual Smoothness metric, which is known to yield a distortion measure that captures the surface smoothness of the time-dependent mesh during the animation. For the calculation of the parameters k_jt, the constrained minimization problem of Eq. 11 is numerically solved, given the channel rate Re- Furthermore, n is calculated from Eq. 6 such that the rate characteristics of the original source signal are met for the particular design of a BOP. The other parameters used in Eq. 6 are given below for the two sequences in the experiments, and are also summarized in Table 1.

TABLE I

ANIMATION SEQUENCE PARAMETERS USED IN THE REDUNDANCY EXPERIMENTS: TELLY &amp;, BQϋNCEBftr-U

<img file="WO2004019619A2_D0015.tif" /><img file="WO2004019619A2_D0016.tif" />

[0067] For the EEP case, a constant k is considered that can be derived directly from the selection of the channel rate, which is set to 15%. For the NP case, all available channel rates to the source are allocated. Finally, an EC scheme was used based on interpolation for the case of UEP with residual losses. In all experiments used L_g = 4.

[0068] The sequences TELLY and BOUNCEBALL were used with density factors of df_τp,Tj_ιV = 0.75 and df_BBALL = 1.0 given by Eq. 2. TELLY consists of 9 nodes (out of which 3 are relatively sparse, and the remaining 6 are complete) and totals 780 frames at 30 Hz as shown in Table I. Its average source bitrate is R_S&gt;TELLY = 220 Kbps. BOUNCEBALL only has 1 complete node and 528 frames at 24 Hz, forming 1 layer of source rate R_{S BALL}⁼ 61 Kbps average. Both sequences have been coded with I-frames at every 15 frames. Roughly 15% of channel coding redundancy was allowed, resulting in total source and channel coding redundancy, resulting in total source and channel rates of TE Y = 253 Kbps and R_BBALL⁼ 70.15 Kbps. Choosing n = 32 the parameters, from Eq. 6 the calculations for each layer's packetization are tabulated in Table I. The value of n is chosen as a compromise between latency and efficiency, since higher n makes the RS codes more resilient, by sacrificing delay and buffer space.

[0069] Sequence. TELLY was split into 3 layers according to the suggested layering method presented in Section V, each consisting of the nodes shown in Table I. Each layer's fraction of the total number of animated vertices in the 3-D mesh is (L₀, L_1; L_j) = (0.48, 0.42, 0.10) on average. This splitting is expected to reflect the source bitrates of each layer proportionally. It was noticed that the suggested layering scheme allocated 2 out of 3 sparse nodes to the same layer, L_v The total number of vertices of these two sparse nodes represents 65% of the vertices in the reference mesh. The third sparse node, Nostril, was allocated to layer L₂, but its individual motion relates to a very small fraction of the model's total number of vertices (« 1.3%). This fact may bear some significance if one desires to relate the node- to-layer allocation (using the VS metric) to the density factor df calculated per layer⁴ (Eq. 2), and to the output bitrates. If such relation exists, a dynamic layering scheme may be developed for applications with such needs.

[0070] Sequence BOUNCEBALL initially contains only one node. The sequence represents a soft ball with inherent symmetry around a center point as its shape implies. The ball also deforms slightly as it bounces. Given the shape symmetry, it was decided to partition the mesh into 2 nodes of equal number of vertices without respect to the VS metric for each node. The logic behind this partitioning is to attempt to verify the effect the VS metric has on the proposed UEP resilience scheme. All other source coding parameters are constant between the two layers, most importantly the quantization step size. It is anticipated that both layers will receive roughly equal average protection bits, so that UEP performance will approach that of EEP.

[0071] Figure 5 depicts a first diagram 502 illustrating VS as a function of the average packet loss rate, P_B, for TELLY. The four curves on the plot represent each suggested resilience method, for the code (31, 22). The average calculated codes for the UEP are as follows

(rounded to nearest integer): (n, k₀) = (31,19), (n, k ) = (31,23), (n, k₂) = (31,28) . It is clear

that UEP, and UEP+EC outperform NP and EEP for medium to high loss rates of P_B &gt; 9%. Recall that the layering is performed in such a way that the lowest layer exhibited high average visual distortion. Since the UEP method allocates higher codes to the lower layer (L₀), better resilience is expected for L₀ at high loss rates. This factor dominates in the average distortion, resulting in better performance. At low loss rates it was noticed that EEP and UEP behave in approximately the same way, as the RS codes are more than sufficient to recover all or most errors. It is also noted that the NP method under conditions of no loss is much better than any other. This is an intuitive result, since source information takes all available channel rate, thus better encoding the signal. It is also worth noticing the effect of EC: the distortion of the UEP+EC scheme is slightly improved over the simple UEP case. This is also expected.

[0072] The results for the (31,27) RS code on sequence TELLY, shown in plot 504 of Figure 5, are similar. Here, the threshold where the UEP methods (with or without EC) take over EEP or NP is around P_B = 7%. Note how the initial NP performance (low P_B's) is steep compared to the (31, 22), highlighting again the fact that channel coding bits are actually 'wasted' since they do not contribute much resilience in this low loss region, at the expense of source rate. The corresponding average codes per layer are:

(n,k₀) = (31,26), («, £,) = (31,28), («, £,) = (31,30) . There is an improvement again in the

UEP method's performance resulting from the error concealment's interpolation algorithm. As this quantity has not been accounted for in the optimization problem it is expected to contribute a small reduction to the visual error.

[0073] Figure 6 shows the results 602 achieved for the same experiment repeated over the

BOUNCEBALL sequence, which was 'symmetrically' layered as described earlier in this section. The same (31, 22) EEP code was used as before for comparison. The graph 602 shows the same trends and relative performances as in TELLY, with UEP4-EC being the one giving the best overall performance. It is noted, however, that the distance of the UEP curves from the EEP ones decreased considerably compared to the TELLY sequence at high P_B's.

The average integer calculated RS codes for the UEP case are:

(n, k₀) = (31,22), («, AΓ_J ) = (31,22) , i.e. equivalent to the EEP case. This may be a surprising

result at the first glance, but careful reasoning suggests that equally balanced layers in terms of the amount of animation they contain (same number of vertices, nodes, very similar motion in the scene, and same encoding parameters) correspond to visually balanced distortions. This is exactly the expected result when layering for the BOUNCEBALL sequence described above. In fact, the real values of kg_t, k_lt computed as the solution to the optimization problem, vary around the average integer value of 22. Furthermore, recall that the original symmetric BOUNCEBALL mesh was partitioned into two arbitrary nodes without consideration to their individual visual distortions, which were assumed to be similar. In fact, the Softball's deformation at the bouncing points reduces the symmetry of the original shape. These facts reasonably explain why the UEP and EEP curves are not accurately fit at higher P_B's as one would normally expect. Finally, it is noted that the UEP+EC method provides a slight, but hardly noticeable, improvement to the visual distortion as in the previous experiment. [0074] The present invention addresses the fundamental problem of how best to utilize the available channel capacity for streaming 3-D wireframe animation in such a way as to achieve optimal subjective resilience to error. In short, the invention links channel coding, packetization, and layering with a subjective parameter that measures visual smoothness in the reconstructed image. On this basis, it is believed that the result may help open the way for 3- D animation to become a serious networked media type. The disclosed methods attempt to optimize the distribution of the bit budget allocation reserved for channel coding amongst different layers, using a metric that reflects the human eye's visual property of detecting surface smoothness on time-dependent meshes. Using this metric, the encoded bitstream is initially partitioned into layers of visual importance, and experimental results show that UEP combined with EC yields good protection against burst packet errors occurring on the Internet.

[0075] Embodiments within the scope of the present invention may also include computer- readable media for carrying or having computer-executable instructions or data structures stored thereon. Such computer-readable media can be any available media that can be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such computer-readable media can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to carry or store desired program code means in the form of computer-executable instructions or data structures. When information is transferred or provided over a network or another communications connection (either hardwired, wireless, or combination thereof) to a computer, the computer properly views the connection, either wired or wireless, as a computer-readable medium. Thus, any such connection is properly termed a computer-readable medium. Combinations of the above should also be included within the scope of the computer-readable media.

[0076] Computer-executable instructions include, for example, instructions and data which cause a general purpose computer, special purpose computer, or special purpose processing device to perform a certain function or group of functions. Computer-executable instructions also include program modules that are executed by computers in stand-alone or network environments. Generally, program modules include routines, programs, objects, components, and data structures, etc. that perform particular tasks or implement particular abstract data types. Computer-executable instructions, associated data structures, and program modules represent examples of the program code means for executing steps of the methods disclosed herein. The particular sequence of such executable instructions or associated data structures represents examples of corresponding acts for implementing the functions described in such steps.

[0077] Those of skill in the art will appreciate that other embodiments of the invention may be practiced in network computing environments with many types of computer system configurations, including personal computers, hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. Embodiments may also be practiced in distributed computing environments where tasks are performed by local and remote processing devices that are linked (either by hardwired links, wireless links, or by a combination thereof) through a communications network. For example, peer-to-peer distributed environments provide an ideal communications network wherein the principles of the present invention would apply and be beneficial. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

[0078] Although the above description may contain specific details, they should not be construed as limiting the claims in any way. Other configurations of the described embodiments of the invention are part of the scope of this invention. Accordingly, the appended claims and their legal equivalents should only define the invention, rather than any specific examples given.