Other Free Encyclopedias » Online Encyclopedia » Encyclopedia - Featured Articles » Contributed Topics from K-O

Middleware for Streaming 3D Meshes - Introduction, 3D Middleware, Results

data channel reliable sub

Hui Li and Balakrishnan Prabhakaran
University of Texas at Dallas, TX, USA

Definition: A 3D middleware between a 3D application layer and the transport layer provides reliable and efficient multimedia streaming.

Introduction

3D meshes have been widely used in multimedia applications such as 3D video gaming, virtual reality and animation databases. Due to the large data size of 3D meshes, the end user typically experiences long delay waiting for a 3D model to download from networks. For example, it requires 168s to download 42 MB “Happy Buddha” model (Large geometric models archive at Georgia Institute of Technology) over a channel offering an average bandwidth of 2 Mbps. To alleviate this limitation, it is desirable to compress 3D meshes first, and then transmit the compressed data over networks. Single-resolution techniques are not suitable for the network transmission since the global view of the model cannot be rendered until the entire model is downloaded. Progressive compression techniques address this issue by sending a base mesh first, and following it with a sequence of refinements when needed. The decoded model quality is improved progressively by adding these refinements. There are two categories of information in a refinement: structural data and geometric data. The structural data contains the connectivity information of the removed/added vertices to their neighbors. To improve the encoding efficiency, instead of the absolute position of a new vertex, an estimation scheme is applied to predict the position of the new vertex based on its existing neighbors. The geometric data contains the difference in geometric coordinates between the absolute and the estimated vertex positions.

Progressive compression techniques are scalable with respect to both network bandwidth and user’s quality requirement. If the channel has a high bandwidth or the user requires a high quality model, more refinements can be transmitted. However, loss of packets during transmission affects the decoded mesh quality in the progressive representation. To meet this gap, error-control schemes must be applied.

Error-control schemes can be broadly divided into three categories: sender-based, network-based and receiver-based. For sender-based error-control methods such as FEC, the sender estimates the channel condition (loss ratio) and inserts redundant bits to protect the 3D data. Unfortunately, these methods have to generate different codes for different channel conditions. For receiver-based error-concealment schemes such as, the receiver can reconstruct the meshes if some of the 3D data is lost during the transmission. The drawback for this method is that the reconstructed mesh cannot guarantee the same mesh connectivity and thus it is only an approximation of the original mesh. In network-based error-control methods, reliable transport protocols such as TCP are used. However, TCP is not real-time streaming friendly due to its retransmission and congestion control mechanisms. On the other hand, RTP (real-time Page 410  transport protocol)/UDP are streaming friendly but are not reliable. Therefore, hybrid protocols have been proposed to take advantages of both TCP/UDP. In these hybrid protocols, the more important 3D data is transmitted over reliable channel and the less important data is transmitted over unreliable channel. However, following issues are not explained in these protocols. 1) How to handle multiple progressively compressed 3D representations such as PM, CPM, PFS and VD. 2) How to identify the relative importance of a given 3D data stream irrespective of its format so that the more important data can be delivered first and reliably. 3) How to consider user’s environment. For example, if the end user device is PDA, it is not necessary to transmit the entire mesh that exceeds PDA’s display capability. 4) How to select the transport channel for the 3D data so that the delay and distortion experienced at the user can be minimized simultaneously. 5) How to construct packets for transmission so that out of sequence packets can be detected and delivered to the 3D applications.

3D Middleware

We propose a generic 3D middleware between the 3D application layer and the transport layer. First, by observing the fact that the structural data affects the quality of the decoded mesh more than the geometric data does, without any changes to the encoder/decoder, we identify and separate the structural data from the geometric data for a given 3D data stream irrespective of its format. Then the geometric data is further decomposed into sub-layers based on the significant bit, and the distortion of the rendered 3D mesh due to the loss of a sub-layer is calculated. Next, a subset of the 3D data stream is selected for the transmission based on the user’s quality requirement. In order to maintain the same mesh connectivity, the base mesh and the selected structural sub-layers are transmitted over reliable channel. For geometric sub-layers, we choose reliable/unreliable channel for the transmission depending on the relative importance to minimize the delay and distortion simultaneously. Finally, we handle packet loss and out of sequence packets by inserting additional fields into packets and synchronize the reliable and unreliable channels by sending an “END” marker on the reliable channel to indicate the end of a refinement. Our simulation results show that the proposed scheme can effectively reduce the delay and distortion experienced at the receiver. Figure 1 depicts the architecture of the proposed middleware.

The proposed middleware consists of the following four modules:

(1) Pre-processor. We proposed a generic pre-processor that works for multiple progressive compression techniques (CPM, PFS and VD). In the pre-processor, we separate the structural and geometric data, decompose the geometric data into sub-layers and then, calculate a distortion metric. The distortion metric represents the importance of a sub-layer to the quality of the decoded mesh. Then, the geometric data is decomposed into different sub-layers and a distortion metric is calculated for each sub-layer. After pre-processing, the 3D data is stored as structural and geometric sub-layers along with their distortion metrics. Note that the pre-processing needs to be performed only once offline for a given 3D data stream.

(2) Minimum set selector. We represent user’s environment diversity by user’s display resolution and rendering capabilities. These parameters are converted into the number of triangles required by the client and communicated to the server. The minimum set selector selects the data set with the minimum size for transmission to satisfy user’s quality requirement. This is a 0/1 knapsack problem and NP-complete. We propose a greedy heuristic algorithm to solve this problem. The generated subset is passed to the reliable set selector.

(3) Reliable set selector. In order to utilize the underlying reliable/unreliable channels efficiently, we select the data set to be transmitted over reliable channel based on the bandwidth and loss ratio. To evaluate the delay and distortion, we assume that the server can monitor the network conditions such as the reliable/unreliable channel bandwidth (Br, Bur). First, to guarantee the same connectivity of the decoded mesh as the original mesh, we transmit the base mesh and all the structural sub-layers over reliable channel. Therefore, approximately one third of the data stream is transmitted over reliable channel. Next, we consider the transmission for the geometric data. Since the loss of the geometric data only affects the quality of the decoded mesh and will not make it crash, we can use unreliable channel for transmission. We define a cost function that computes the total effect of the delay and distortion for a given bandwidth, loss ratio and geometric sub-layers. We generate the delivery list with the minimum cost function and pass it to the packet constructor. In addition, it is necessary to consider the dynamics of the network. If Br, Bur or 1 changes, the reliable set selector calculates a new delivery list. If the number of the geometric sub-layers between the new delivery list and the old delivery list is greater than the given threshold, the reliable set selector sends a revised set of sub-layers to the packet constructor.

(4) Packet constructor. Packet constructor at the server segments the sub-layers into packets and uses the specified transport channels for delivery so that the stream constructor at the receiver can reconstruct the compressed 3D data stream. In order for the receiver to detect out of order packets and lost packets over unreliable channel, additional information must be added to each packet. Three fields are inserted into each packet by the packet constructor: refinement index, sub-layer index and vertex index. Vertex index is the number of vertices that have been transmitted. The stream constructor uses these three fields to uniquely position a Page 412  received packet and detect out of order packets. Since we use reliable channel and unreliable channel alternatively, the stream constructor has to know the end of the transmission of a refinement, and then it can construct the 3D compressed data stream and deliver it to the decoder. Therefore, synchronization between reliable channel and unreliable channel is necessary. Here, we propose to use an “END” marker for each refinement to indicate that the transmission for the refinement is complete and ready to be assembled and delivered. For each refinement, we transmit the data over unreliable channel first, and followed by the data over reliable channel. When the transmission over reliable channel is complete for a refinement, an “END” marker is sent over reliable channel. Upon receiving the “END” marker, the stream constructor begins assembling the received data and then delivers it to the decoder. Once a refinement is delivered to the decoder, the stream constructor discards all the delayed packets that belong to this delivered refinement.

Results

Effectiveness of minimum set selector

To show the effectiveness of the minimum set selector, we compare the proposed selection process with a sequential selection process. The sequential selection process picks sub-layers sequentially in the ordinary order. Tables 1 and 2 show the comparison of the selected data size between the proposed selection and the sequential selection for “bunny” and “horse”, respectively. Given a distortion requirement Dr, the data size generated by the proposed selection process is less than or equal to the one generated by the sequential selection scheme. For example, given Dr= 10 for “bunny” model, if we choose sub-layers sequentially in the refinement order, the size of the selected data set is 1109 KB. With the proposed selection process, the size of the data set is reduced to 913 KB. The proposed selection process saves 18% of the data size to be transmitted. The reason is that some sub-layers selected by the sequential method do not have the relative importance as much as the ones selected by the proposed selection process.

It should be noted that the proposed selection scheme is a “heuristic” algorithm; the generated data set may not be the optimal solution with the constraints. For example, from Table 1, for Dr = 40 and Dr = 230, the data set generated by the proposed selection process is the same as the one generated by the sequential scheme. Similarly, Table 1 shows the data size picked by the proposed selection scheme is less than or equal to the one picked by the sequential scheme.

Effectiveness of reliable set selector

The simulations are performed on wireless networks. Single-hop mode is used for the transmission from the server to the client. We use Qualnet, developed at Scalable Network Technologies, as the wireless network simulator. Wireless users are randomly distributed over a 350 × 350 area and node one is designated as the server. The physical bandwidth is 2 Mbps. We assume that the network drops packets randomly. For each simulation case, we ran 100 times and took the average distortion as the expected distortion.

To show the effectiveness of the proposed reliable set selection scheme (“Proposed”), the performance of following three schemes are compared.

(1) “Reliable all”. The base mesh and all the selected sub-layers are transmitted with reliable channel.

(2) “Hybrid”. It transmits the base mesh, the selected structural sub-layers with reliable channel and the selected geometric sub-layers with unreliable channel.

(3) “Optimized”. The proposed method presented in “Reliable Set Selector”.

Figures 2 and 3 show the delay-distortion curves for the above three methods with different loss ratios. We chose to transmit the entire mesh. “Hybrid” has the worst performance. The reason is that the distortion of the geometric sub-layers in the coarse refinements is relatively large. If we transmit such sub-layers over unreliable channel, the users will experience large distortion. As loss ratio decreases, this distortion can be reduced. This indicates that such geometric sub-layers should be transmitted over reliable channel

“Reliable all” performs better than “Hybrid” but worse than “Optimized” in the range from 0-50s. The reason is that the proposed method uses reliable channel to transmit the geometric sub-layers with large relative importance value to reduce the distortion at the user and the same time, it uses unreliable channel to transmit the geometric sub-layers with small relative importance value to reduce the delay. Moreover, with unreliable Page 415  channel, the server can transmit more sub-layers than “Reliable all” given the same time frame. Therefore, with the proposed reliable set selector, the 3D compressed data stream can be delivered in such way that both small distortion and low delay can be achieved. Because our scheme obtains both the minimum delay and distortion, if the user prefers distortion to delay, one needs to trade delay for it.

Midgley, Thomas [next] [back] Michelson, Albert Abraham

User Comments

Your email address will be altered so spam harvesting bots can't read it easily.
Hide my email completely instead?

Cancel or