Model-based view extrapolation for interactive virtual reality systems

[0002] This application claims the benefit of U.S. provisional application No. 60/147,419, filed Aug. 6, 1999, which is hereby incorporated by reference herein in its entirety.

[0003] This invention relates to video compression techniques, and more particularly, to video compression techniques suitable for use with three-dimensional content such as three-dimensional virtual reality environments.

[0004] With the increasing popularity of network-based applications, compression of synthetic animation image sequences for efficient transmission is more important than ever. For long sequences, the latency time of downloading the compressed file may be prohibitive, even if the overall compression ratio is high. A better network-based compression scheme may involve partitioning the compressed sequence into two parts. The first part, or header, may be small enough to be downloaded within an acceptable initialization time, while the second part may be transmitted as a stream. The compressed data may be broken up into a stream of data that may be processed along the network pipeline—i.e., the compressed data may be transmitted from one end and received, decoded, and displayed at the other end. Streaming necessarily requires that all the pipeline stages operate in real time. Network bandwidth is the most constrained resource along the pipeline. The main challenge is therefore to reduce the stream bandwidth enough to accommodate the network bandwidth constraint.

[0005] Standard video compression techniques like MPEG, are generally insufficient for steaming in low-bandwidth environments. For example, average MPEG frames are typically about 2-6K bytes in size for moderate frame resolutions. Assuming a network with a sustained transfer rate of 2K bytes per second, a reasonable quality of a few frames per second cannot be achieved.

[0006] A significant improvement in compression ratio is still necessary for streaming video in real time.

[0007] It is an object of the present invention to provide improved video compression schemes.

[0008] It is a further object of the present invention to provide video compression schemes that allow high-quality content to be streamed over relatively low-bandwidth network connections.

[0009] In accordance with the present invention, a video compression system is provided.

[0010] The system may include a video source for providing video. The video source may be based on a real-life camera. For example, the video source may be a real-life camera that provides digital images and range or distance information. The video source may also involve the generation of animations or other three-dimensional virtual reality content. Such content may include, for example, a three-dimensional virtual world that is presented from the point-of-view of a user at a virtual camera position. Model and animation data may be provided by the video source. If desired, other suitable video capture or playback equipment may be used as the video source.

[0011] Video content from the video source may be encoded by an encoder and decoded by a decoder. Video decoded by the decoder may be presented to a user on a display device.

[0012] If desired, the encoder may be implemented on a server and the decoder may be implemented on a client. The server and client may communicate over a relatively low-bandwidth network connection (e.g., a standard dial-up modem connection on the Internet or the like). A user at the client may interact with the encoder in real time by providing user inputs (e.g., desired movements in the virtual reality environment) to the encoder over the network connection.

[0013] Further features of the invention, its nature and various advantages will be more apparent from the accompanying drawings and the following detailed description of the preferred embodiments.

[0014] FIG. 1 is a schematic diagram of the video compression scheme in accordance with the present invention.

[0015] FIG. 2 shows an illustrative encoding process in accordance with the present invention.

[0016] FIG. 3 shows an illustrative decoding process in accordance with the present invention.

[0017] FIG. 4 is a schematic diagram of an illustrative embodiment of a client-server video compression arrangement that supports real-time interactivity for a user in accordance with the present invention.

[0018] FIG. 5 is a diagram showing how neighboring pixels with dissimilar depth need not be included in a weighted average that uses the values of adjacent high-quality pixels to estimate the value of a low quality pixel in accordance with the present invention.

[0019] FIG. 6 is a diagram showing how a pixel may include contributions from pixels in multiple reference frames in accordance with the present invention.

[0020] FIG. 7 is a diagram of an illustrative video compression process that uses depth information (Z) in accordance with the present invention.

[0021] FIG. 8 is a diagram illustrating the use of future reference frames during reconstruction of compressed video in accordance with the present invention.

[0022] FIG. 9 is a diagram of an illustrative navigation graph in accordance with the present invention.

[0023] A diagram illustrating a system 10 that may be used to support video compression techniques in accordance with the present invention is shown in FIG. 1. System 10 may include a video source 12, an encoder 14, a decoder 16, and a display device 18. Video source 12 and encoder 14 may be implemented using one computer (e.g., a server) and decoder 16 and display device 18 may be implemented using another computer (e.g., a client). Video source 12, encoder 14, decoder 16, and display device 18 may also be implemented on a single computer or two or more computers that communicate with each other, but which do not use a client-server architecture.

[0024] Video may be supplied by video source 12. Video source 12 may be any suitable source of video. For example, video source 12 may provide video that is captured from a real-life video camera. Video source 12 may also provide video that is generated from an animation tool. For example, an animation tool may be used to create a three-dimensional virtual reality world that is described by a model M. The video provided by source 12 may include a sequence of video frames E_i, each of which corresponds to a different view of the virtual world. Each frame may correspond to a different state of the environment. For example, a user located at decoder 16 may be interacting with the virtual reality environment and each view may correspond to a different position of the user's point-of-view (e.g., a different position of a user's virtual camera within the virtual environment). Animated objects that appear in the user's field-of-view may also have different positions and appearances in different frames.

[0025] In order to reduce the bandwidth requirements for transmitting the video frames to decoder 16, decoder 16 may be used to estimate the frames being displayed on display 18 based on a relatively small number of transmitted reference frames and model information. Reference frames may either be selected from a video sequence or may represent a model state that neighbors the video sequence.

[0026] Initially, C₀, a compressed version of an initial exact frame E₀, and at least a portion of the modeling information sufficient for calculating the three-dimensional position at all elements in E₀(e.g., modeling information M₀) may be transmitted to decoder 16.

[0027] Encoder 14 may approximate reference frame A₁based on corrected reference frame C₀and model information M₀and based on model information M₁. Model information M_imay be any information that provides a three-dimensional location for each point in the video frames E_i(e.g., a polygonal model including animations or a Z-buffer).

[0028] The three-dimensional mapping used to create approximated views A_iand A_jmay be based on a model-based back-projection technique. Model-based approaches are significantly better for exploiting inter-frame coherence than techniques such as MPEG. With the model-based approach, motion compensation (e.g., a two-dimensional mapping from the new approximated frame A₁to reference frame C₀—also called back-projection) may be computed by client 22 and need not be transmitted to client 22 from server 20.

[0029] At video source 12, an exact reference frame E₁may be created. For example, a rendering application or engine that is implemented on the computer equipment on which encoder 14 is located may be used to render frame E₁.

[0030] Rather than sending complete reference frames from encoder 14 to decoder 16, system 10 uses an arrangement in which difference reference frames D_ior compressed difference reference frames D_i′ may be transmitted to decoder 16 from encoder 14.

[0031] The difference frames D_i′ may be compressed more than the reference views E_i, which reduces the amount of data that needs to be transmitted over the network. Moreover, the server 20 need only correct reference frames, which are constructed at a lower frequency than the display frames (e.g., {fraction (1/20)}th of the frequency).

[0032] At encoder 14, a difference frame, D₁=E₁−A₁may be created based on the exact reference frame E₁and the approximated reference frame A₁. If desired, difference frame D₁may be compressed using JPEG compression or other lossy compression schemes or a lossless compression technique to produce compressed difference frame D₁′.

[0033] It is not necessary to include all pixels. Rather, pixels may be selected for transmission based on their “quality.” For example, only pixels of high quality may be transmitted and other pixels may be discarded. High quality pixels may be defined as those with a high visibility (i.e., pixels that may fill holes or gaps or the like) and those with a high scaling factor (closeness). The use of quality criteria is described in more detail below.

[0034] As described in more detail below, a suitable packing scheme may be used before compressing difference frames such as difference frame D₁. For example, difference frames D_imay be divided into sections that contain the pixels selected as described above. The remaining pixels may be discarded. The sections may be packed together and compressed when forming difference frame D_i′. Before using such a packed difference frame to generate a corrected reference view, the packed difference frame may be uncompressed and then unpacked.

[0035] If the difference frame is compressed using lossy compression before being transmitted to client 22, the corrected reference frames C_ithat are computed by client 22 will not be identical to the exact reference frames E_i. In this situation, server 20 may be used to calculate the corrected reference frames C_i, like client 22, by adding the compressed difference frames D_i′ to the approximated views A_i. This ensures that the state of client 22 is always available to server 20.

[0036] The unpacked difference reference view D₁′ may be used in encoder 14 to calculate a corrected reference frame C₁based on the approximated frame A₁, because C₁=A₁+D₁′.

[0037] The corrected reference frame C₁may then be used by encoder 14 to calculate an additional approximated reference frame A₂based on model information M₂. The process may continue at encoder 14, with each successive compressed difference reference frame D_i′ being used to create a corresponding corrected reference frame C_iand by creating approximated reference frames A_ibased on the preceding values of C₀. . . C_i−1and M₀. . . M_i−1and new modeling information M_i. Difference frames D_imay be created based on exact reference frames E_i.

[0038] Similarly, when creating approximated frames A_iand A_j, the source pixels being relied upon in the corrected reference frames C₀. . . C_i−1may be chosen based on the quality of each pixel. In particular, pixels may be selected based on whether they are located on near objects or far objects. The nearness of pixels in a view is a criteria that may be referred to as closeness or scaling. Pixels may also be selected based on whether they are filling a hole or gap (e.g., based on their visibility). If desired, both scaling and visibility may be used to judge the quality of the pixels being used to create approximated views and difference views.

[0039] With the arrangement of FIGS. 1-3, a scene's modeling data (e.g., three-dimensional and animation data) may used to approximate (interpolate) views from reference views using three-dimensional mapping. The mapped views may be constructed by dividing frames into sections. Each section of a frame may be based on an underlying geometric model. For each section of a frame being constructed, the reference frame to be used may be chosen from a pool of multiple reference frames according to quality criteria. Each frame section may be three-dimensionally mapped from a set of the selected reference frames. The set may be selected based on the quality criteria. This is described in more detail below.

[0040] On the decoder side, reference frames are constructed and corrected in the same way that reference frames are constructed and corrected at the encoder. Each approximated reference frame may be based on model state information M_ifrom video source 12 and may be based on previous corrected reference frames C₀. . . C_i−1and model information M₀. . . M_i−1. Difference frame D_i′ may be unpacked and used to correct approximated reference frames A_i, thereby producing a corrected reference frame C_i.

[0041] Corrected reference frames C₀. . . C_i−1and model information M₀. . . M_i−1may be used to estimate a series of approximated display frames A_jbased on model state information M_j. If desired, model state information M_jmay be based on user inputs.

[0042] If desired, model states M_imay be selected for their suitability in generating reference frames. Model states M_jand display frames A_jare determined by the video sequence being displayed.

[0043] When decoder 16 creates approximated frames A_iand A_j, the source pixels being relied upon in the corrected reference frames C₀. . . C_i−1may be chosen based on the quality of each pixel.

[0044] The encoding process performed by encoder 14 is shown in more detail in FIG. 2. As shown in FIG. 2, model state M_imay be combined with corrected reference frames C₀through C_i−1and model information M₀. . . M_i−1to create an approximated reference frame A_i. Approximated reference frame A_imay be subtracted from an exact reference frame E_ito create difference reference frame D_i. Frame E_imay be generated at video source 12. Difference reference frame D_imay be compressed to create compressed difference reference frame D_i′.

[0045] The decoding process performed by decoder 16 is shown in more detail in FIG. 3. As shown in FIG. 3, model state M_imay be combined with previous corrected reference frames C₀through C_i−1and model information M₀. . . M_i−1to create approximated reference frame A_i. Compressed difference reference frame D_i′ may be used to correct approximated reference frame A_ito create corrected reference frame C_i. Corrected reference frames C₀. . . C_i−1and model information M₀. . . M_i−1may be used to extrapolate approximated display frames A_jbased on model state information M_j.

[0046] Local scaling factors may be used as criteria for measuring the quality of three-dimensional mappings from a reference frame using a geometric model. The scaling factor may vary for each pixel in a constructed image and may be a measure of the amount of stretching involved a given mapping from a reference frame to an approximated frame. A high scaling factor may result in a blurred and therefore low-quality result. The scaling factor may be computed from the matrix norm 2 of the partial derivative matrix of the mapping at a certain pixel neighborhood.

[0047] Assume that the virtual reality environment is described by a polygonal geometric model, textures, and a number of light sources. Given a view (frame) and a set of view-dependent textures (corrected reference frames), it is desirable to select the highest quality texture for each visible polygon. The quality of the source texture is related to the area covered by the projection of each polygon in the source frame (corrected reference frames). Thus, a per polygon local scaling factor may be used to estimate the areas in the source texture that locally shrink or expand when mapped onto the source frame (corrected reference frame). When the scaling factor is less than or equal to one, the source frame may be considered to be adequate for generating a target frame. As the scaling factor increases above 1, more and more blurriness appears in the target images, so the source texture may be considered to be less and less adequate. This per polygon texture quality factor may be used to select the best source texture out of the available set of view-dependent textures (corrected reference frames). If the best source is above a predetermined threshold, a new texture (corrected reference frame) may be required. However, a successful streaming of the textures may guarantee that there will always be one available texture whose quality factory is satisfactory.

[0048] The maximal value of the scaling factor in a particular polygon in the source frame may be estimated for a given target frame (approximated reference frame A_i). The scaling factor may be defined independently of the visibility of the polygon. The polygon may be mapped from the source to the target by a linear transformation or a non-linear transformation.

[0049] In the linear case, let A be a square matrix corresponding to a linear transformation. The scaling factor of a linear transformation is the 2-norm of the matrix A, i.e., the maximum 2-norm of Av over all unit vectors v.

[0050] max∥Av∥₂

[0051] ∥v∥₂=1

[0052] It can be shown that the 2-norm of A equals the square root of λ_max, the largest eigenvalue of A^TA. In the case of two-dimensional linear transformations, where A is a 2 by 2 matrix, a closed-form expression for λ_maxmay be provided. Let a_ijdenote the elements of A and e_ijthe elements of A^TA: $\begin{array}{cc}A=\left(\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right)A^{T}A=\left(\begin{array}{cc}{e}_{11}& e_{12}\\ e_{21}& e_{22}\end{array}\right)& \left(1\right)\end{array}$

[0053] The eigenvalues of the matrix A^TA are the roots of the polynomial det(A^TA−λI), where I is the identity matrix. In the two-dimensional case, λ_maxis the largest root of the quadratic equation

[0054] (e₁₁−λ) (e₂₂−λ)−e₁₂e₂₁=0.  (2)

[0055] Thus, $\begin{array}{cc}{\lambda }_{\max }=\frac{e_{11}+e_{22}+\sqrt{{\left(e_{11}+e_{22}\right)}^2-4\left(e_{11}{e}_{22}-e_{12}{e}_{21}\right)}}{2}& \left(3\right)\end{array}$

[0056] Expressing the elements e_ijin terms of the elements a_ijyields $\begin{array}{cc}{A}^{T}A=\left(\begin{array}{cc}{a}_{11}^2+a_{21}^2& a_{11}{a}_{12}+a_{21}{a}_{22}\\ a_{11}{a}_{12}+a_{21}{a}_{22}& a_{12}^2+a_{22}^2\end{array}\right)& \left(4\right)\end{array}$

[0057] and finally, defining S=½(a₁₁²+a₁₂²+a₂₁²+a₂₂²²), yields

[0058] λ_max=S+{square root over (S  (5)

[0059] Handling non-linear transformations, such as projective transformations, requires measuring the scale factor locally at a specific point in the image by using the partial derivatives of the transformation at that specific point. The partial derivatives may be used as the coefficients of a linear transformation.

[0060] The source and target image coordinates of a point may be denoted by x₀, y₀, and x₁,y₁respectively. The three-dimensional location of that point in target camera coordinates may be denoted by x, y, z. This gives: $\begin{array}{cc}{\left(x,y,z\right)}^T=\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right){\left(x_0,y_0,1\right)}^T& \left(6\right)\\ {\left(x_1,y_1\right)}^T=\frac{1}{z}{\left(x,y\right)}^T& \left(7\right)\end{array}$

[0061] or explicitly, $\begin{array}{cc}{x}_1=\frac{{\mathrm{ax}}_0+{\mathrm{by}}_0+c}{{\mathrm{gx}}_0+{\mathrm{hy}}_0+i}{y}_1=\frac{{\mathrm{dx}}_0+{\mathrm{ey}}_0+f}{{\mathrm{gx}}_0+{\mathrm{hy}}_0+i}& \left(8\right)\end{array}$

[0062] The partial derivatives of the above mapping at (x₁, y₁) define its gradient, which is a linear transformation: $\begin{array}{cc}A=\left(\begin{array}{cc}\partial x_1/\partial x_0& \partial x_1/\partial y_0\\ \partial y_1/\partial x_0& \partial y_1/\partial y_0\end{array}\right)=\frac{1}{z^2}\left(\begin{array}{cc}\mathrm{za}-x_{1}g& \mathrm{zb}-x_{1}h\\ \mathrm{zd}-y_{1}g& \mathrm{ze}-y_{1}h\end{array}\right)& \left(9\right)\end{array}$

[0063] In cases where the field of view is small, and there is only a little rotation of the plane relative to the source and target views, the following approximation can be used. The transformation of the plane points from source to target image can be approximated by:

[0064] x₁=a+bx₀cy₀+gx²₀+hx₀y₀

[0065] y₁=d+ex₀+fy₀+gx₀y₀+hy²₀

[0066] This is called a pseudo 2D projective transformation and results in: $\begin{array}{cc}A=\left(\begin{array}{cc}b+2{\mathrm{gx}}_0+{\mathrm{hy}}_0& c+{\mathrm{hx}}_0\\ e+{\mathrm{gy}}_0& f+{\mathrm{gx}}_0+2{\mathrm{hy}}_0\end{array}\right)& \left(11\right)\end{array}$

[0067] To estimate the maximal scaling factor, the gradient can be computed at the three vertices of a triangle. In cases where the triangle is small enough, even one sample (at the center of the triangle) can yield a good approximation.

[0068] Image-based rendering techniques including the techniques of the present invention, may exhibit artifacts such as holes and overlaps due to mappings between frames that are non one-to-one functions. Holes, referred to as visibility gaps, are areas of the approximated frame that are not covered by the reference view. Overlaps are areas in the approximated frame that are mapped by more than one area in the reference. Overlaps may be prevented using depth values to determine the presence of hidden surfaces. Holes may be more handled using multiple reference frames, as described below.

[0069] Another suitable quality criteria that may be used in addition to the scaling factor is visibility. Visibility gaps are areas visible in the approximated frames that are not visible in the associated reference frames. Pixels in the approximated frames that reside in visibility gaps may be considered to have an extremely low quality when mapped from the reference frame. Pixels in gaps are usually hidden behind closer objects in the reference frame or are outside of the viewing frustrum.

[0070] If desired, a combination of both the scaling factor and visibility criteria may be used to determine the quality of three-dimensional mappings from a reference frame. A pixel, which is invisible in the reference frame (C_i) may receive the lowest quality value. The quality of pixels that are visible may be determined by the scaling factor. Computational effort may be minimized by dividing a frame into small patches. The scaling factor may be computed at the center of each patch and given to all pixels in the patch. A convenient method of partitioning the images into patches is to use the underlying three-dimensional model. The projection of each polygon in the constructed image may be considered to be a separate patch and the projection of each polygon may include the visibility of the pixel in the reference and the local scaling factor.

[0071] If desired, a wider field-of-view (FOV) may be used for reference frames (C_i) than the display field-of-view presented to the client-side user. A wider reference field-of-view may prevent holes around the edges of the three-dimensionally mapped frame caused by a change in the virtual camera viewing angle between two reference frames.

[0072] Another approach involves locating low quality pixels in the approximated frame and approximating them based on the values of high quality neighbors. This approach may be used in combination with approaches based on multiple reference frames or wider reference fields-of-view. If desired, a requirement for similar depth values may be used to ensure that neighboring pixels belong to the same surface as the approximated pixel. A weighted average for the texture (or color or red-green-blue or RGB) values may be computed for all such neighbors. The weights that are used may be the inverse of the distance between the neighbor and the approximated pixel. As shown in FIG. 5, with this approach, values from nearby high-quality pixels may be included in the weighted average, but neighbors with dissimilar depths that are therefore not part of the same surface as the low quality pixel are excluded.

[0073] As shown in FIG. 6, a plurality of available reference frames (C₀-C_i) may be used to three-dimensionally map a new approximated frame A. A pool of available corrected reference frames (C₀-C_i) may be selected. For each pixel, P_j, in the approximated frame A, the qualities (Q₀-Q_i) of all three-dimensional mappings to the pool reference frames (C₀-C_i) may be computed according to chosen criteria (e.g., visibility and scaling). The reference frame C_khaving the highest quality value Q_kmay be chosen as the source for the pixel P_j. If desired, more than one reference frame may be used as a source for the pixel and blended using the quality values Q₀-Q_ias weights in a weighted average. This may ensure that the mapping of the pixel is smooth relative to the frame A for the new point-of-view.

[0074] The quality criteria may also be used to reduce bandwidth requirements. The quality associated with the three-dimensional mapping of each pixel in the approximated frame may be computed regardless of the number of reference frames used. Pixels that have been mapped with a high quality may be omitted from the difference frame to save bandwidth.

[0075] A further bandwidth reduction may be achieved by using a packing algorithm for the remaining pixels. A suitable packing algorithm is described in Y. Mann et al., “Selective Pixel Transmission for Navigating in Remote Virtual Environments,” (Eurographics 97). The packing algorithm rearranges the remaining (low quality) difference frame pixels into a smaller rectangular area, while maintaining correlation among neighboring pixels. A packed image may be compressed significantly better than an unpacked image when using lossy techniques such as JPEG. Pixels omitted from the residual are not corrected in the corrected reference frame. These pixels contain no additional information relative to their source reference frames. Accordingly, such pixels are not marked to be used as a source for subsequent three-dimensional mappings, at least while their source reference frames are available for three-dimensional mappings.

[0076] The approximated view A may be constructed by back-projecting. Back-projecting may be used with a polygonal model. Because the correspondence between two perspective views is a projective map, the model may be rendered by applying a projective mapping rather than a perspective mapping. This projective map can be expressed by a linear transformation in homogenous space and can be implemented by rational linear interpolation, which requires divisions at each pixel.

[0077] An alternative to the inclusion of the geometric model in the data set involves treating depth data (also known as Z-buffer data or data on the distance from the optical plane at the real or virtual camera at the user's point-of-view) as another image band in addition to the standard color bands (RGB bands). The Z-band may be approximated by mapping the Z-band from corrected reference frames using a three-dimensional mapping. The Z-band's residual may be computed and included in the data set, as shown in FIG. 7. Because of the addition of the depth band, the exact reference frame E_i, the approximated reference frames A_i, the difference frames D_iand D_i′, and the corrected reference frames C_iinclude both RGB data for color information and Z data for depth information. No separate model state information (M_i) is necessary with this scheme, because the mappings may be calculated from the embedded depth information. A Z-buffer residual may be efficiently compressed using an algorithm with direction encoding, as described by B. K. Guenter et al. in “Motion Compensated Compression of Computer Animation Frames” in Computer Graphics Proceedings, Annual Conference Series, 1993. When a Z-buffer is used instead of a geometric model, however, fast scan-line algorithms may not be used. Rather, pixels need to be forward-mapped from the source and smeared in the target image to prevent holes. Ray tracing algorithms may also be used. Such solutions are generally slower and more complex than scan-line algorithms.

[0078] A data set that includes model state information (e.g., geometric and animation data) and difference frames may be transmitted from encoder 14 to decoder 16. The data set may be compressed and packed. The data set may be streamed to decoder 14 as needed based on user inputs (e.g., based on a user's virtual point-of-view when navigating through a virtual world) and based on animation requirements (e.g., based on requirements that certain objects in the virtual reality world are moving or changing and are not static when viewed by the user).

[0079] Additional aspects of the invention may be understood with reference to the following illustrative examples.

[0080] Real-time Interactive Client-Server System

[0081] A real-time interactive client-server system 19 is shown in FIG. 4. Video is generated on a server 20 and provided to a client 22 over a network. The network may be, for example, a relatively low-bandwidth network such as the Internet as accessed by conventional dial-up modems or the like.

[0082] The user may roam in a virtual reality environment that is presented to the user on display device 30. The user may navigate using any suitable user input device 32, such as a mouse, trackball, joystick, keyboard, touch pad, touch screen, etc.

[0083] Client 22 may send a camera point-of-view (user input) to server 20 at fixed intervals (e.g., at a frequency of once per second). In response, server 20 may use detailed model information DM_iand texture information T to render an exact frames E_iusing the camera position information as shown in FIG. 4. Server 20 may generate a difference frame D_i′ and may immediately transmit frame D_i′ to client 22. An advantage of the arrangement of FIG. 4 is that it places few computational requirements on server 20, because difference frames D_i′ need only be rendered at a relatively low frequency.

[0084] Detailed model state information DM_imay be used by video source 24 of server 20 to render exact frames (views) E_iof the virtual reality environment. The frames may correspond to model states that include information on the user's virtual camera point-of-view and the state of any animation in the virtual environment (e.g., the position of a moving object in the user's field-of-view). The camera point-of-view information may be transmitted from the user input device 32. If desired, an extrapolator 34 may be used to extrapolate from the user's current position and the extrapolated information sent to video source 24 for use in generating frames. Texture information T may also be used by video source 24 when rendering frames E_i.

[0085] Initially, client 22 may transmit an initial point-of-view (user input) to video source 24. Video source 24 may render an exact reference frame E₀for the initial point-of-view. Video source 24 may send frame E₀to client 22 accompanied by the portion of the simplified three-dimensional model (M₀) that is needed for that point of view.

[0086] After initialization, the user may navigate through the virtual reality world by entering coordinates of new points-of view (user inputs). Client 22 may use three-dimensional mapping to create display frames based on the user inputs (i.e., based on the user's point-of-view information). The user inputs may be transmitted from client 22 to server 20 periodically (e.g., once per second, etc.). If desired, client 22 may use an extrapolator 34 to approximate a future point-of-view using a linear or higher-order extrapolation of the user point-of-view. Approximating future points-of-view in this way may help to reduce areas in the three-dimensionally mapped frames that are not covered by available reference views. After receiving the extrapolated point-of-view information from extrapolator 34, server 20 may use three-dimensional mapping to create a corresponding approximated reference view A_ithat is identical to the one generated by client 22. Server 20 may then render an exact reference view E_ifor the extrapolated point-of-view using its fully textured high-detailed model (T, DM_i). Subtracting the approximated frame (A_i) from the exact frame (E_i) creates difference frame information that may be transmitted to client 22.

[0087] After rendering an exact reference frame E_i, encoder 26 may generate a data set that is transmitted to client 22 over the communications network (e.g., over the Internet).

[0088] Decoder 28 may generate a new corrected reference frame C_i. Reference frames C₀. . . C_i−1and model information M₀. . . M_i−1may be combined with the locally-available data M_ito construct subsequent approximated reference frame A_i. Because the reference frame A_ithat is constructed by decoder 28 is only an approximation, the data set provided to the client may include a difference (residual) frame D_i′ that is used to generate a corrected reference frame C_i.

[0089] Difference frames represent the difference between the approximated reference frames A_iand the exact reference views E_ithat are rendered by the server 20.

[0090] At client 22, approximated display frames A_jmay be generated by three-dimensional mapping of corrected reference frames C₀. . . C_i−1and model information M₀. . . M_i−1. The camera positions or any other user-controlled parameter for model state M_jmay be determined in real time using user inputs from user input device 32. This allows display frames A_jto be displayed on display device 30 without latency. Latency may be avoided due to the decoupling between the construction of display frames A_jand the data set produced by encoder 26. The server 20 need only transmit sufficient information to client 22 to maintain a pool of corrected reference frames (C₀. . . C_i−1) and associated model information M₀. . . M_i−1on client 22 with camera positions sufficiently close to those used for display frames A_jto ensure the availability of high-quality sources for the three-dimensional mapping between frames C₀. . . C_i−1and frames A_j.

[0091] If desired, simplified model state information M_imay be transmitted to client 22 from server 20, rather than detailed model state information DM_i. The virtual reality environment may include textured model information (i.e., detailed model DM_iand textures T) stored at server 20. The transmitted model (i.e., simplified model state information M_i) need only include geometry and animation information, but not textures. This may result in a substantial reduction in the bandwidth required to transmit model state information from server 20 to client 22, because texture-space information may be significantly larger than geometry space information for a many virtual reality environments.

[0092] Server 20 need only transmit model data M_iwhen new models enter the user's viewing frustrum or when a new level of detail is required for an existing model. The transmitted model may be losslessly compressed or may be compressed using lossy compression. So long as model M_iis sufficient for calculating the necessary three-dimensional mappings, the transmitted model information (M_i) may be a simplified version of the true model (DM_i). The animation information to be applied to the model in the time and space visible to the user at the client 22 may be included in model information M_i. If desired, this animation information may be losslessly compressed, may be compressed using lossy compression, or may be approximated.

[0093] Computer-Generated Video Compression

[0094] A synthetic (computer-generated) video compression scheme may be used in which encoder 14 of FIG. 1 prepares a file offline that is to be decoded later by decoder 16 (FIG. 1) and displayed on display device 18. A client-server arrangement need not be used to play back video—a non-client-server system may be used. If desired, the encoder 14 and decoder 16 may reside on the same computer.

[0095] The three-dimensional model of the rendered scene and video frames, which may be generated by a three-dimensional animation tool such as 3D Studio Max or LightWave. Frames in the video sequence are also associated with model states M_j, which include a camera point-of-view and animation data.

[0096] Encoder 14 may choose reference frames out of the video sequence or reference frames that represent a model state that neighbors the video sequence. References may be sampled from the sequence at a frequency lower than the video display rate. Encoder 14 may prepare a data set containing residuals (difference frames) for each of the reference frames. The residuals describe the difference between the exact reference view and an approximated reference view which is three-dimensionally mapped from previous corrected references. Each reference data set may also contain the three-dimensional model parts and animation needed for the approximation of the reference view. Because the user does not supply any inputs, the data set must contain the camera point-of-view information for each frame in the video sequence including the reference frames.

[0097] Decoder 16, reading the reference data set file, may reconstruct the reference views. Approximated reference views A_imay be approximated by three-dimensional mapping from previously corrected reference views C₀. . . C_iand model information M₀. . . M_i−1. The approximated reference views may each be combined with a residual (difference frame) D_i′ to arrive at a corrected reference view C_i. Once the entire set of corrected reference views C_iis reconstructed, the decoder 16 may proceed to reconstruct the entire sequence of video frames A_jfor display based on model states M_j. Model states M_jdescribe the states of the model and the camera for each frame of the video sequence. Decoder 16 may use the entire set of corrected reference views C₀. . . C_iand model information M₀. . . M_i−1to 3D-map each frame in the video sequence. “Holes” in the 3D-mapping are rare, because decoder 16 uses future three-dimensionally mapped reference frames as well as past three-dimensionally mapped reference frames. The number of low quality pixels in the three-dimensional mapping that need to be approximated from their neighboring pixels is therefore low.

[0098] This non-interactive scheme may also be used for the compression of real-life video sequences (i.e., video that is not computer generated). For example, available photogrametric methods for extracting a 3D-model and animation of a scene from a video sequence, can be used. If desired, depth data (Z-buffer data) may be included in the data set instead of using a three-dimensional model. Real-life video cameras that have range scanners may be used to generate data for this compression scheme.

[0099] The compressed data set generated by the encoder 14 in this scheme may be streamed. Streaming is important for broadcasting video over the Internet or for viewing video sequences over the Internet that are more than a few seconds long. Each reference frame may be reconstructed before any data for subsequent reference frames is read by decoder 16. Due to the streaming environment, the entire set reference frames will not be available for generating non-reference frames. If desired, however, the three-dimensional mapping of a given video frame may be delayed until one or two (or more) reference views from the future have been reconstructed. This technique alleviates most of the artifacts associated with “holes” in the three-dimensional mapping, while supporting a streaming environment.

[0100] This playback approach is illustrated in FIGS. 8a, 8b, and 8c. In FIG. 8a, frame C₀has been reconstructed at the client. In FIG. 8b, frames C₀and C₁have been reconstructed and therefore playback has been initiated and frames are currently being played at time t₁, which is between C₀and C₁. In FIG. 8c, frame C₂has been reconstructed and playback has advanced to time t₂.

[0101] Client-Server System Based on Offline Data Sets

[0102] An interactive client-server web system may be provided in which the client-side user roams in a remote virtual reality environment held in the server, but in which the server does not render views of the environment or encode a data set online. Instead, an encoder prepares numerous data sets offline, each of which corresponds to a short walkthrough in the environment. These data sets may be stored in a database residing on the server. The user may navigate in the virtual reality environment by choosing from the prepared walkthroughs (e.g., by clicking on on-screen signs or other options). The appropriate walkthrough may then be extracted by the server from the database and streamed to the client and displayed for the user.

[0103] Although this method somewhat restricts the interactive possibilities of the user, it requires significantly lower computing and graphic server capabilities than a fully-interactive approach. The server may be, for example, a relatively simple HTTP file server that is capable of simultaneously serving hundreds or thousands of clients using a standard personal computer hardware platform.

[0104] The short walkthroughs prepared by the encoder may define the edges of a directional graph that covers all areas in the virtual reality environment that are of potential interest to the user. A number of walkthroughs may end in the same single view (e.g., an exact reference frame). This view may also be the first view of a number of different walkthroughs. Such a view defines a vertex in the graph and may also be referred to as a junction. Between junctions, multiple reference frames (e.g., multiple exact reference frames, corrected reference frames, difference reference frames, and approximated reference frames) may be associated with each edge. Walkthroughs ending and starting at a specific junction are, respectively, the incoming edges and outgoing edges of that vertex. The user navigates by choosing a path in the directional graph, which is made up of seamlessly concatenated walkthroughs. FIG. 9 is a graphic representation of an illustrative navigational graph of this type. The short walkthrough BA is outgoing from junction B and incoming to junction A.

[0105] A convenient user interface for navigation inside a walkthrough graph involves using hotspots on the video frame. For example, clicking on a sign saying “dining room” will direct the server to stream a walkthrough to the client that takes the user towards a virtual dining room in the virtual reality environment. If desired, navigation buttons such as “turn left” or “turn right” may be provided. By selecting such a button while at a certain junction, the user may choose a preencoded walkthrough from the available outgoing walkthroughs from that junction. For example, when the user selects the turn left option, a video sequence for a left turn may be provided.

[0106] Each individual walkthrough may be encoded and a data set prepared using the approaches described above in connection with computer-generated video compression techniques. The first and last views of each walkthrough (the vertices of the graph) may always be chosen as reference views. If desired, other views in each walkthrough may be chosen as references, e.g., by sampling the walkthrough views at a frequency lower than the display rate.

[0107] The first reference view of a walkthrough is usually also the last reference of a previously displayed walkthrough. In these cases the data associated with the first reference can be omitted from the data set. Additionally, all parts of the geometric model needed for the first reference may already reside at the client side and may therefore be omitted from the data set.

[0108] With this type of arrangement, real-world video sequences can be used as described above in connection with computer-generated video compression. However, it may be desirable to give special attention to ensuring that walkthroughs end and begin at nearly the exact same view. For example, real-life cameras may be mounted on physical tracks or the like so that they may travel the same paths of the graph through which the user will navigate in the virtual reality environment.

[0109] If desired, more interactivity may be supported to enable the user to roam around (and not simply on) the predefined path prepared by the encoder. This may be accomplished because the views that are three-dimensionally mapped for display on the client side need not be only reference views (i.e., the model states M_jof FIG. 1 need not be located on the same path as the reference model states M_iand may vary in viewing angles, etc.). Typically, most of the reconstructed views will not be reference views. If the user is allowed to change the camera viewing angle as well as its position, than the field-of-view of the reference frames is preferably much wider than the field-of-view displayed to the user. In the relatively extreme case in which the user may freely choose any viewing angle, the field-of-view for each reference is preferably 360 degrees (i.e., a panorama).

[0110] Although the examples described herein use a difference image as a correction data set, other types of correction data sets may be used instead of a difference image or in addition to a difference image.

[0111] The three-dimensional models described herein may generally be formed using primitives such as polygons and textures. If desired, other methods of representing a three-dimensional environment may be used such as voxels, nurbs, etc.

[0112] Moreover, different quality criteria may be used when three-dimensionally mapping a pixel or a group of pixels. For example, the ratio between the areas a certain patch covers in source versus target views may be used as a quality criteria.

[0113] The foregoing is merely illustrative of the principles of this invention and various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention.