System and method of streaming 3-D wireframe animations

Abstract

Optimal resilience to errors in packetized streaming 3-D wireframe animation is achieved by partitioning the stream into layers and applying unequal error correction coding to each layer independently to maintain the same overall bitrate. The unequal error protection scheme for each of the layers combined with error concealment at the receiver achieves graceful degradation of streamed animation at higher packet loss rates than approaches that do not account for subjective parameters such as visual smoothness.

Claims

1. A method comprising: partitioning, via a processor, a three-dimensional wireframe mesh corresponding to a video scene according to (1) a natural object within the three-dimensional wireframe mesh and (2) a motion of the natural object, to yield a first partition comprising the natural object and a second partition; organizing the first partition and the second partition into respective layers based on a first visual smoothness value for the first partition and a second visual smoothness value associated with the second partition; and generating one or more bitstreams including the respective layers for transmission.

2. The method of claim 1, wherein the second partition comprises a second natural object having a second motion.

3. The method of claim 2, further comprising: computing the first visual smoothness value for the first partition; and computing the second visual smoothness value for the second partition.

4. The method of claim 1, further comprising: applying unequal error protection to the respective layers, wherein the unequal error protection applied to each layer of the respective layers is based on a respective bitrate value for each layer of the respective layers.

5. The method of claim 1, wherein each layer of the respective layers comprises one of a node and a group of nodes within the three-dimensional wireframe mesh.

6. The method of claim 1, further comprising encoding a particular layer in the respective layers to be resilient to packet errors.

7. The method of claim 1, wherein a number of nodes within a portion of the respective layers is associated with an output bit rate of the portion.

8. A system comprising: a processor; and a computer-readable storage medium storing instructions which, when executed by the processor, cause the processor to perform operations comprising: partitioning a three-dimensional wireframe mesh corresponding to a video scene according to (1) a natural object within the three-dimensional wireframe mesh and (2) a motion of the natural object, to yield a first partition comprising the natural object and a second partition; organizing the first partition and the second partition into respective layers based on a first visual smoothness value for the first partition and a second visual smoothness value associated with the second partition; and generating one or more bitstreams including the respective layers for transmission.

9. The system of claim 8, wherein the second partition comprises a second natural object having a second motion.

10. The system of claim 9, wherein the computer-readable storage medium stores additional instructions which, when executed by the processor, cause the processor to perform operations further comprising: computing the first visual smoothness value for the first partition; and computing the second visual smoothness value for the second partition.

11. The system of claim 8, wherein the computer-readable storage medium stores additional instructions which, when executed by the processor, cause the processor to perform operations further comprising: applying unequal error protection to the respective layers, wherein the unequal error protection applied to each layer of the respective layers is based on a respective bitrate value for each layer of the respective layers.

12. The system of claim 8, wherein each layer of the respective layers comprises one of a node and a group of nodes within the three-dimensional wireframe mesh.

13. The system of claim 8, wherein the computer-readable storage medium stores additional instructions which, when executed by the processor, cause the processor to perform operations further comprising: encoding a particular layer in the respective layers to be resilient to packet errors.

14. The system of claim 8, wherein a number of nodes within a portion of the respective layers is associated with an output bit rate of the portion.

15. A computer-readable storage device storing instructions which, when executed by a processor, cause the processor to perform operations comprising: partitioning a three-dimensional wireframe mesh corresponding to a video scene according to (1) a natural object within the three-dimensional wireframe mesh and (2) a motion of the natural object, to yield a first partition comprising the natural object and a second partition; organizing the first partition and the second partition into respective layers based on a first visual smoothness value for the first partition and a second visual smoothness value associated with the second partition; and generating one or more bitstreams including the respective layers for transmission.

16. The computer-readable storage device of claim 15, further comprising producing a three-dimensional packetized streaming signal representative of a scene comprising animation associated with the respective layers.

17. The computer-readable storage device of claim 15, further comprising partitioning the respective layers according to a visual importance of each layer of the respective layers.

18. The computer-readable storage device of claim 15, wherein a number of nodes within a portion of the respective layers is associated with an output bit rate of the portion.

19. The computer-readable storage device of claim 15, wherein the computer-readable storage device stores additional instructions which, when executed by the processor, cause the processor to perform operations comprising: applying unequal error protection to the respective layers, wherein the unequal error protection applied to each layer of the respective layers is based on a respective bitrate value for each layer of the respective layers.

20. The computer-readable storage device of claim 19, wherein the unequal error protection comprises optimizing a distribution of a bit budget allocation amongst the respective layers.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) 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:

(2) FIG. 1A is a block diagram of a 3-D Animation codec;

(3) FIG. 1B is a block diagram of a decoder;

(4) FIG. 2 is a comparative plot of distortion metrics including PSNR, Hausdorff Distance and Visual Smoothness;

(5) FIG. 3A represents a flowchart of method of error resilient wireframe streaming;

(6) FIG. 3B illustrates a flowchart according to an aspect of the invention;

(7) FIG. 4 is a comparative plot of three error concealment methods for sequence for wireframe animation TELLY;

(8) FIG. 5A is a comparative plot of Visual smoothness (VS) transmitted and decoded frames of 3 layers of the wireframe animation TELLY;

(9) FIG. 5B is another comparative plot of VS; and

(10) FIG. 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

(11) 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 relied on objective measures such as PSNR in lieu of those that take subject effects into account.

(12) 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.

(13) 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.

(14) The vertices m.sub.j of a time-dependent 3-D mesh form the indexed set M.sub.t={m.sub.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.sub.j, y.sub.j, z.sub.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.sub.t, as:

(15) $M_t=\left[\begin{array}{cccc}{\mathrm{��}}_{1,t}& {\mathrm{��}}_{2,t}& \mathrm{.Math.}& {\mathrm{��}}_{n,t}\\ {\mathrm{��}}_{1,t}& {\mathrm{��}}_{2,t}& \mathrm{.Math.}& {\mathrm{��}}_{n,t}\\ {\mathrm{��}}_{1,t}& {\mathrm{��}}_{2,t}& \mathrm{.Math.}& {\mathrm{��}}_{n,t}\end{array}\right]$

(16) 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 defined in the virtual reality markings language (VRML). The position matrix corresponding to the i.sup.th node is denoted by N.sub.i,t. Note that without loss of generality, the vertex matrix can now be expressed as:
M.sub.t=[N.sub.1,tN.sub.2,t . . . N.sub.k,t]
for k such nodes. For notational convenience, the terms N.sub.i,t (i=1, 2, . . . , k) are used both for representing a matrix and to refer to the i.sup.th node as well. The objective of the 3D-Animation compression algorithm is to compress the sequence of matrices M.sub.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.sub.t 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:
D.sub.t={d.sub.it=m.sub.itm.sub.n0, i=1, 2, . . . ,p(pn):d.sub.it0}

(17) Following this notation, the above can be expressed with a displacement matrix, D.sub.t, as:

(18) $D_t=M_t-M_0{D}_t=\left[\begin{array}{cccc}{\mathrm{��}}_{1,t}-{\mathrm{��}}_{1,0}& {\mathrm{��}}_{2,t}-{\mathrm{��}}_{2,0}& \mathrm{.Math.}& {\mathrm{��}}_{p,t}-{\mathrm{��}}_{p,0}\\ {\mathrm{��}}_{1,t}-{\mathrm{��}}_{1,0}& {\mathrm{��}}_{2,t}-{\mathrm{��}}_{2,0}& \mathrm{.Math.}& {\mathrm{��}}_{p,t}-{\mathrm{��}}_{p,0}\\ {\mathrm{��}}_{1,t}-{\mathrm{��}}_{1,0}& {\mathrm{��}}_{2,t}-{\mathrm{��}}_{2,0}& \mathrm{.Math.}& {\mathrm{��}}_{p,t}-{\mathrm{��}}_{p,0}\end{array}\right]$
or equivalently, using node matrices:
D.sub.t=[F.sub.1,tF.sub.2,t . . . F.sub.l,t](1)
where F.sub.i,t the displacement matrix of node i, for l such nodes (i=1, 2, . . . , l). Note that D.sub.t's dimension is reduced to pn compared to M.sub.t, since D.sub.t does not contain vertices for which the displacement on all axes is zero. Note, too, that lk holds, in the event that no vertices in a node get displaced (F.sub.i;t=0). In 3D-Animation terminology, sparse animations are referred to as those sequences with p<n and l<k, whereas if p=n and l=k the animation is called dense. It is evident that if an encoder is capable of controlling parameters p and l, it can generate a layered bitstream (by adjusting parameter l), 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:

(19) $\begin{array}{cc}df=\frac{1}{F}\frac{1}{k}\underset{f=1}{\overset{F}{.Math.}}\underset{j=1}{\overset{l}{.Math.}}\frac{P_{jf}}{n_{jf}},\mathrm{with}lk\mathrm{and}pn.& \left(2\right)\end{array}$
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.fwdarw.n and l.fwdarw.k, then df.fwdarw.l, therefore a complete animation.

(20) 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.sub.0, 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.

(21) In the 3D-Animation codec's context, an I-frame describes changes from the reference model M.sub.0 to the model at the current time instant t. A P-frame describes the changes of a model from the previous time instant t1 to the current time instant t. The corresponding position and displacement matrices for I and P frames are denoted respectively by M.sub.t.sup.I, M.sub.t.sup.P, D.sub.t.sup.I, D.sub.t.sup.P.

(22) FIG. 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 {circumflex over (D)}.sub.t1.sup.P. (Equivalently for encoding an I-frame the predicted matrix is {circumflex over (D)}.sub.t1.sup.I where at t=0 is the displacement matrix for the reference model.) Then, the prediction error E.sub.t, i.e. the difference between the current displacement matrix and the predicted one 106 is computed 102 and quantized 104 (.sub.t). Finally, the quantized samples are entropy coded (C.sub.t) using an adaptive arithmetic coding algorithm 110 to handle the unknown data statistics. This predictive scheme prevents quantization error accumulation.

(23) A DPCM decoder 120 is shown in FIG. 1B. The decoder 120 first decodes arithmetically the received samples 122 (C.sub.t) and computes the decoded samples 124, 126 ({circumflex over (D)}.sub.t). 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.

(24) The disclosure mentions above that D.sub.t's dimension is reduced to pn compared to M.sub.t, 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.sub.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.sub.i,t=0, i[1 . . . l], the displacement matrix D.sub.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).

(25) 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.sup.q) and encodes k q-bit information symbols into a codeword of n such symbols, i.e. n2.sup.q1. A sender needs to store copies of k information packets in order to calculate nk 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.

(26) 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.sub.GB and p.sub.BG fully describe the model, but since they are not sufficiently intuitive, the model can be expressed using the average loss probability P.sub.B, and the average burst length L.sub.B, as:

(27) $\begin{array}{cc}{P}_B=\mathrm{Pr}\left(B\right)=\frac{p_{\mathrm{GB}}}{p_{\mathrm{GB}}+p_{\mathrm{BG}}}& \left(3\right)\\ L_B=1\text{/}{p}_{\mathrm{BG}}.& \left(4\right)\end{array}$

(28) 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 nk packets are lost within a BOP, and it is called the block error rate, P.sub.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:

(29) $\begin{array}{cc}{P}_{\mathrm{BER}}=\underset{m=n-k+1}{\overset{n}{.Math.}}P\left(m,n\right)& \left(5\right)\end{array}$

(30) The average loss probability P.sub.B and the average loss burst L.sub.B 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.

(31) 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 v1 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.sup.v1|1). The gap distribution function G(v) gives the probability of a gap length greater than v1, i.e. G(v)=Pr(0.sup.v1|1). In state B of our model all packets are lost, while in state G all packets are received, yielding:

(32) $\left(v\right)=\{\begin{array}{cc}1-p_{\mathrm{BG}},& v=1\\ {p_{\mathrm{BG}}\left(1-p_{\mathrm{GB}}\right)}^{v-2}{p}_{\mathrm{GB}},& v>1\end{array}G\left(v\right)=\{\begin{array}{cc}1,& v=1\\ {p_{\mathrm{BG}}\left(1-p_{\mathrm{GB}}\right)}^{v-2},& v>1\end{array}$

(33) Let R(m, n) be the probability of m1 packet losses within the next n1 packets following a lost packet. This probability can be calculated from the recurrence:

(34) $R\left(m,n\right)=\{\begin{array}{cc}G\left(n\right),& m=1\\ \underset{v=1}{\overset{n-m+1}{.Math.}}\left(v\right)R\left(m-1,n-v\right),& 2mn\end{array}$
Then, the block error density function P (m, n) or probability of m lost packets within a block of n packets is given by:

(35) $P\left(m,n\right)=\{\begin{array}{cc}1-\underset{v=1}{\overset{n}{.Math.}}P\left(m,v\right),& m=0\\ \underset{v=1}{\overset{n-m+1}{.Math.}}{P}_{B}G\left(v\right)R\left(m,n-v+1\right),& 1mn\end{array}$
where P.sub.B is the average error probability.

(36) 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.sub.B, L.sub.B 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 minimizes the visual distortion.

(37) 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:

(38) (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 list 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.

(39) (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.

(40) (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.

(41) 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.

(42) 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.sub.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.sub.p, the data frame rate in a BOP F.sub.BOP, and the RS code (n, k).

(43) Intuitively, for a BOP consisting of F.sub.BOP data frames, with Sp bytes long packets, at FR frame rate, the total source and channel bitrate R is given by:

(44) $\begin{array}{cc}R=\frac{n.Math.\mathrm{FR}.Math.\mathrm{Sp}}{F_{\mathrm{BOP}}}& \left(6\right)\end{array}$

(45) This equation serves as a guide to the design of efficient packetization schemes by appropriately balancing the parameters F.sub.BOP, n and S.sub.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.

(46) 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.sub.t at time t and its decoded equivalent {circumflex over (M)}.sub.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.sub.t and {circumflex over (M)}.sub.t in such a way that every point M.sub.t lies within the distance H (M.sub.t, {circumflex over (M)}.sub.t) of every point in {circumflex over (M)}.sub.t and vice versa. This can be expressed as:

(47) 0$\begin{array}{cc}H\left(M_t,{\hat{M}}_t\right)=\max \left(h\left(M_t,{\hat{M}}_t\right),h\left({\hat{M}}_t,M_t\right)\right)\mathrm{where}h\left(M_t,{\hat{M}}_t\right)=\underset{m_t{M}_t}{\max }\underset{{\hat{m}}_t{\hat{M}}_t}{\min }||m_t-{\hat{m}}_t||,& \left(7\right)\end{array}$
and is the Euclidean distance between the two vertices, m.sub.t and {circumflex over (m)}.sub.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.

(48) FIG. 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.

(49) One attempt that was made in the direction of using surface smoothness was reported by Karni and Gotsman as being undertaken whilst evaluating their spectral compression algorithm for 3-D mesh geometries. See, Zachi Karni 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.sub.i is:

(50) $\mathrm{GL}\left(v_i\right)-v_i-\frac{jn\left(i\right)l_{ij}^{-1}{v}_j}{jn\left(i\right)l_{ij}^{-1}}$
where n(i) is the set of indices of the neighbors of vertex i, and l.sub.ij 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.sub.t {circumflex over (m)}.sub.t are the vertex sets of meshes M.sub.t, {circumflex over (M)}.sub.t respectively, and n the set size of M.sub.t, {circumflex over (M)}.sub.t):

(51) $\begin{array}{cc}||M_t-{\hat{M}}_t||=\frac{1}{2n}\left(||m_t-{\hat{m}}_t||+||\mathrm{GL}\left(m_t\right)-\mathrm{GL}\left({\hat{m}}_t\right)||\right)& \left(8\right)\end{array}$

(52) 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.

(53) The VS metric requires connectivity information such as the adjacent vertices of every vertex m.sub.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.

(54) 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.

(55) 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.sub.0. This is the layer that should be more resilient to packet errors than other layers. Subsequent importance layers L.sub.1, . . . , L.sub.M are created by correspondingly subsequent nodes, or group of nodes, in the VS order.

(56) 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.

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

(58) The nature of 3-D animation layers disclosed herein is not always cumulative in the same sense. Decoding layer L.sub.j (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.sub.0 . . . L.sub.j1, but adds animation details to the animated model by, for example, adding animation to more vertices in the model.

(59) 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 L.sub.j1 and the invisible part to layer L.sub.j. In the case of a static camera (and where no interactivity is allowed) layer L.sub.j 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.sub.j 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.sub.j does not refine the animation of the visible node of the hair in layer L.sub.j1. It contains additional animation data for the invisible vertices. This provides an example result of the partitioning method.

(60) 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 L.sub.j 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.

(61) FIG. 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).

(62) 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.

(63) FIG. 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.

(64) The expected distortion of the animation at the receiver at time t is the sum of the product quantities P.sub.jt.Math.D.sub.jt, where j is the layer index, D.sub.jt is the visual distortion incurred by missing information in layer j at time t, and P.sub.jt is the probability of having an irrecoverable packet loss in layer j. By the way we constructed the layers, the probabilities P.sub.jt are independent, and a burst packet loss in a layer contributes its own visual distortion D.sub.jt in the decoded sequence. Formally, the expected visual smoothness VS.sub.(t) of an animation at the decoder at time t can be expressed as:

(65) $\begin{array}{cc}{\mathrm{VS}}_{\left(t\right)}=\underset{j=0}{\overset{L-1}{.Math.}}{P}_{jt}{D}_{jt},t& \left(9\right)\end{array}$
where L is the number of layers. In the equation above, P.sub.jt is the block error rate P.sub.BER as given by Eq. 5, or the probability of losing more than nk.sub.j packets in layer j. Using the block error density function P (m, n), the following is derived:

(66) $\begin{array}{cc}{P}_{jt}=\underset{m=n-k_{jt}+1}{\overset{n}{.Math.}}P\left(m,n\right)& \left(10\right)\end{array}$
From Eqs. 9 and 10, VS.sub.(t) can be described as:

(67) $\begin{array}{cc}\mathrm{VS}\left(t\right)=\underset{j=0}{\overset{L-1}{.Math.}}\underset{m=n-k_{jt}+1}{\overset{n}{.Math.}}P\left(m,n\right)D_{jt},t& \left(11\right)\end{array}$

(68) 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.sub.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.sub.jt that need to be calculated at every time t, that follow the conditions 0k.sub.jtn and

(69) $\underset{j=0}{\overset{L-1}{.Math.}}\left(n-k_{\mathrm{jt}}\right)=R_C/q$
where R.sub.C 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.

(70) The anticipated behavior of the model for P.sub.B=0 is to produce equal values for k.sub.jt's, whereas in high P.sub.B's unequally varying k.sub.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.

(71) 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.

(72) FIG. 4 is a graph 400 illustrating the relative performances of three error concealment methods adapted to the experimental parameters of this work, namely P.sub.B=[0 . . . 30] and L.sub.B=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 L.sub.B=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 nk.sub.jt BOP packets. In fact, the k.sub.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.

(73) 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.

(74) 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.sub.jt, the constrained minimization problem of Eq. 11 is numerically solved, given the channel rate R.sub.C. 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.

(75) TABLE-US-00001 TABLE 1 ANIMATION SEQUENCE PARAMETERS USED IN THE REDUNDANCY EXPERIMENTS: TELLY & BOUNCEBALL Sequence TELLY df.sub.TELLY 0.75 Nodes 9 Frame Rate 30 Hz Source Rate 220 Kbps Channel Rate 33 Kbps Frames 780 Layer 0 UpperLip LowerLip Tongue Layer 1 Skin Teeth Layer 2 EyeLash EyeBrow EyeCornerNostril BOUNCEBALL Df.sub.BBALL 1.0 Nodes 1 Frame Rate 24 Hz Source Rate 61 Kbps Channel Rate 9.15 Kbps Frames 528 Layer 0 Bounceball TELLY BBALL L.sub.0: S.sub.P 264 200 P.sub.BOP 16 35 L.sub.1: S.sub.P 264 200 P.sub.BOP 19 35 L.sub.2: S.sub.P 150 N/A P.sub.BOP 50 N/A

(76) 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.sub.B=4.

(77) The sequences TELLY and BOUNCEBALL were used with density factors of df.sub.TELLY=0.75 and df.sub.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.sub.S,TELLY=220 Kbps. BOUNCEBALL only has 1 complete node and 528 frames at 24 Hz, forming 1 layer of source rate R.sub.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 R.sub.TELLY=253 Kbps and R.sub.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.

(78) 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.sub.0, L.sub.1, L.sub.2)=(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.sub.1. 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.sub.2, 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.sub.L, calculated per layer.sup.4 (Eq. 2), and to the output bitrates. If such relation exists, a dynamic layering scheme may be developed for applications with such needs.

(79) 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.

(80) FIG. 5A depicts a first diagram 502 illustrating VS as a function of the average packet loss rate, P.sub.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.sub.0)=(31,19), (n, k.sub.1)=(31,23), (n, k.sub.2)=(31,28). It is clear that UEP, and UEP+EC outperform NP and EEP for medium to high loss rates of P.sub.B>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.sub.0), better resilience is expected for L.sub.0 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.

(81) The results for the (31,27) RS code on sequence TELLY, shown in plot 504 of FIG. 5B, are similar. Here, the threshold where the UEP methods (with or without EC) take over EEP or NP is around P.sub.B=7%. Note how the initial NP performance (low P.sub.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.sub.0)=(31,26),(n,k.sub.1)=(31,28),(n,k.sub.2)=(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.

(82) FIG. 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 UEP+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.sub.B's. The average integer calculated RS codes for the UEP case are: (n,k.sub.0)=(31,22),(n,k.sub.1)=(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 k.sub.0t, k.sub.1t 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.sub.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.

(83) 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.

(84) 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.

(85) 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.

(86) 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.

(87) 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.