Progressive Frame Patching for FoV-based Point Cloud Video Streaming

MPEG has considered point cloud coding (PCC) and recommended two different approaches [30]. The V-PCC approach projects a point cloud frame into multiple planes and assembles the projected planes into a single 2D frame, and code the resulting sequence of frames using previously established video coding standard HEVC. The G-PCC approach represents the geometry of all the points using an octree, and losslessly represents the octree using context-based entropy coding. The color attributes are coded following the octree structure as well using a wavelet-like transform. By leveraging the efficiency of HEVC, especially in exploiting temporal redundancy through motion compensated prediction, the V-PCC approach is more mature and is currently more efficient than the G-PCC for dense point clouds. However, V-PCC does not allow selective transmission of regions intersecting with the viewer’s FoV or objects of interests. It is also not efficient for sparse clouds such as those captured by LiDAR sensors. The spatial scalability can be indirectly enabled by coding the projected 2D video using spatial scalability, but this does not directly control the distance between the points and cannot be done at the region level.

A point cloud can be coded using an octree which is recursively constructed: the root node represents the entire space spanned by all the points, which is equally partitioned along the three dimensions into $2\times 2\times 2$ cubes; the root has eight children, each of which is the root of a sub-octree representing each of the eight cubes. The recursion stops at either an empty cube, or the maximum octree level $L$. Each sub-octree rooted at level $l$ represents a cube with side lengths that are $1/2^{l}$ of the side lengths of the original space. To code the geometry, the root node records the $(x,y,z)$ coordinates of the center of the space, based on which the coordinates of the center of any cube at any level are uniquely determined. Consequently, each non-root node only needs one bit to indicate whether the corresponding cube is empty or not. For the octree in Fig. 1b, the nodes with value $1$ at the three levels represent one, two and three non-empty cubes with side lengths of $1/2$, $1/4$ and $1/8$ in Fig. 1a, respectively. All the non-empty nodes at level $l$ collectively represent the geometry information of the point cloud at the spatial granularity of $1/2^{l}$. This makes octree spatially scalable: with one more level of nodes delivered, the spatial resolution doubles (i.e., the distance between points is halved). The color attributes of a point cloud are coded following the octree structure as well, with each node stores the average color attributes of all the points in the corresponding cube. Scalable color coding can be achieved by only coding the difference between a node and its parent. The serialized octree can be further losslessly compressed using entropy coding. With MPEG G-PCC, at each tree level $l$, the status of a node ($0$ or $1$) is coded using context-based arithmetic coding, which uses a context consisting of its neighboring siblings that have been coded and its neighboring parent nodes to estimate the probability $p$ that the node is $1$.

Considering the limited viewer Field-of-View (FoV) (dependent on the 6-DoF viewpoint), occlusions between objects and parts of the same object, and the reduced human visual sensitivity at long distances, only a subset of points of a PCV frame are visible and discernible to the viewer at any given time. FoV-adaptive PCV streaming significantly reduces PCV bandwidth consumption by only streaming points visible to the viewer at the spatial granularity that is discernible at the current viewing distance. To support FoV-adaptive streaming, octree nodes are partitioned into slices that are selectively transmitted for FoV adaptability and spatial scalability. Each slice consists of a subset of nodes at one tree level that are independently decodable provided that the slice containing their parents is received. Without considering FoV adaptability, one can simply put all nodes in each tree level into a slice to achieve spatial scalability. The sender will send slices from the top level to the lowest level allowed by the rate budget. To enable FoV adaptability, a popular approach known as tile-based coding is to partition the entire space into non-overlapping 3D tiles and code each tile independently using a separate tile octree. Only tiles falling into the predicted FoV will be transmitted. To enable spatial scalability within a tile, we need to put the nodes at each level of the tile octree into a separate slice. As illustrated in Fig. 1c, each sub-octree rooted at level $L_{T}$ represents a 3D-tile with side length of $1/2^{L_{T}}$. Within each tile sub-octree, nodes down to the $L_{B}$ level are packaged into a base layer slice, and nodes at the lower layers are packaged into additional enhancement layer slices.

When the streaming server is close to the viewer, one can conduct reactive FoV-adaptive streaming: the client collects and uploads the viewer’s FoV to the server; the server renders the view within the FoV, and streams the rendered view as a 2D video to the viewer. To facilitate seamless interaction and avoid motion sickness, the rendered view has to be delivered with short latency (e.g. $<$20 ms) after the viewer movement, the so called Motion-to-Photon (MTP) latency constraint [1]. To address the MTP challenge, we consider predictive streaming that predicts the viewer’s FoVs for future frames and prefetches tiles within the predicted FoV [7, 8, 9].

Most of the existing FoV-adaptive streaming solutions can be categorized as Sequential-Decision-Making (SDM): at some time point $\tau$ before the playback deadline $t$ of a frame, one predicts the viewer FoV at $t$, downloads tiles falling into the predicted FoV at video rates determined by some rate adaptation algorithm, then repeats the process for the next frame. $t-\tau$ is the time interval for both FoV prediction and frame pre-feteching, which is upper bounded by the client side video buffer length. To achieve smooth streaming, a long pre-fetching interval is preferred to absorb the negative impact of bandwidth variations. However, FoV prediction accuracy decays significantly at long prediction intervals. We have studied the optimal trade-off for setting the buffer length for on-demand streaming of 360^o video in [35, 36].

Scalable PCV coding opens up a new dimension to reconcile the conflicting desires for long streaming buffer and short FoV prediction interval. It allows us to progressively download and patch tiles: when a frame’s playback deadline is still far ahead, we only have a rough FoV estimate for it, and will download low resolution slices of tiles overlapping with the predicted FoV; as the deadline approaches, we have more accurate FoV prediction, and will patch the frame by downloading additional enhancement slices for tiles falling into the predicted FoV. Progressive streaming is promising to simultaneously achieve streaming smoothness and robustness against bandwidth variations and FoV prediction errors. On one hand, as shown in Fig. 2, each tile in each segment is downloaded over multiple rounds, the interval of which is $\Delta$. For example, tiles of $seg_{i+3}$ are downloaded in both round $i\Delta$ and round $(i+1)\Delta$. Traditional methods download the segment only once in round $i\Delta$ based on the FoV prediction at this moment. The benefit of downloading $seg_{i+3}$ in two rounds is that FoV prediction in round $(i+1)\Delta$ is more accurate than in round $i\Delta$. Therefore, the bandwidth can be allocated to the tiles that would be more likely viewed by user. A segment consists of $S$ frames with the total video duration of $\Delta$. Within each round, multiple segments are downloaded simultaneously. And the final rendered quality of each tile is a function of the total downloaded rate (thanks to the scalable coding, there is minimal information redundancy between the multiple progressive downloads). The final rendered quality is less vulnerable to network bandwidth variations and the FoV prediction errors at individual time instants. On the other hand, tile downloading and patching are guided by FoV predictions at multiple time instants with accuracy improving over time. If a tile falls into the predicted FoV in multiple rounds, the likelihood that it will fall into the actual FoV is high, and its quality will be reinforced by progressive downloading; if a tile only shows up once in the predicted FoV when its playback time is still far ahead, the chance for it to be in the actual FoV is small. Fortunately, the bandwidth wasted in downloading the low-resolution slices is low.

Progressive streaming conducts Parallel-Decision-Making (PDM). For a tile $k$ in the frame to be rendered at $t$, we prefetch it in the previous $I$ rounds, from $t-I$ to $t-1$. Let $r_{i}(t,k)$ denote its download rate in round $t-i$. The final rate for this tile is $\sum_{i=1}^{I}r_{i}(t,k)$. Meanwhile, at download time $\tau$, all tiles of frames with playback time from $\tau+1$ to $\tau+I$ are being downloaded/patched at rates $\{r_{i}(\tau+i,k),1\leq i\leq I,\forall k\}$, and the total rate is bounded by the available bandwidth $B(\tau)$, i.e.,

Suppose $Q(r,d)$ is the rendered quality of a tile at rate $r$ when viewed from distance $d$, and $\tilde{p}_{\tau+i,k}$, $\tilde{d}_{\tau+i,k}$ are the predicted view likelihood and view distance for tile $k$ of frame to be rendered at time $\tau+i$. One greedy solution for bandwidth allocation at download time $\tau$ is to maximize the expected quality enhancements for all the active frames, based on the current FoV estimations:

, where $w_{i}$ is a decreasing function of $i$, considering that FoV estimate accuracy drops for far away frames.

In this section, we explain in detail the proposed tile utility model $Q(r,d)$ in Equation (IV-B). Tile quality depends on its angular resolution $f_{ang}$, which is the number of points per degree that are visible to the user within the tile. There are many subjective studies about the quality of rendered images or videos, but most of them only consider the impact of rate, while very few consider the distance between the viewer and the object, which can be very dynamic in PCV streaming. A subjective study in [8] suggests that users’ QoE changes significantly when they view a rendered point cloud object at different distances. The authors showed a reasonable curve telling the relations between utility, rate and viewing distance. Unfortunately, it didn’t provide a specific utility model. In our work, we try to find a specific tile utility function with respect to viewing distance and tile rate that generates the same trend of curve in [8]. For the traditional 2D video frames/tiles, which is assumed to be viewed from a fixed distance, we can infer the direct mapping from rate to quality, which is usually a logarithm function. However, it is not that clear how the rate and viewing distance simultaneously impact the perceived quality of point cloud tiles. A quality model of image with respect to both distance and resolution was proposed in [37], but it doesn’t directly fit with point cloud video. Nevertheless, it is inspired from [37] that the perceived quality for an object depends on the angular resolution, which depends on the viewing distance and physical size of the object, as well as image resolution. Following [37], we assume that the perceived quality of a viewed tile is logarithmically increasing with the angular resolution $f_{ang}$, which is the number of points per degree within the tile. With more and more points inside the tile, the per-degree utility increases but more and more slowly. Let $log(c\cdot f_{ang})$ be the per-degree quality of a tile, we assume that the perceived quality of a tile that covers $\theta$ degree in either horizontal or vertical direction is

where $c$ is a constant factor to be determined by the saturation threshold. As shown in Fig. 3, each tile is a suboctree, and $f_{ang}$ is decided by the level of detail (LoD) which is the suboctree’s height $H$ within the tile, and the viewer’s span-in-degree $\theta$ across the tile:

where $d$ is the distance between the viewer and the tile, and $wid$ is the physical side length of a tile. Therefore, the tile utility model is:

where $M=wid\cdot 180/\pi$.

To achieve a level of detail (LoD) $H$, all nodes up to level $H$ of the tile suboctree has to be delivered, which will incur a certain rate (the total number of bits to code a tile to level $H$). We have coded several test PCVs using MPEG G-PCC and found that the LoD is logarithmically related to the rate. Due to tile diversity, the data rate needed to code octree nodes up to level $H$ is highly tile-dependent. In other words, given a coding rate budget $r$, the achievable LoD is tile-dependent. Let $H_{i,k}(r)$ be the rate-LoD mapping for tile $k$ within frame $i$, we assume

where the parameters $a_{i,k},b_{i,k}$ are obtained by fitting the actual rate data for the tiles coded using G-PCC. Substituting this expression into (2) yields:

Note that tile utility is not necessarily $0$ at $r=0$, because there is possibly one point inside the tile. There’s only one parameter to be decided: $c$, which controls the shape of the curve. We decide its value by reasoning that the utility should saturate at some point even if we keep increasing rate and/or distance. This is due to human visual acuity: generally we cannot resolve any two points denser than $60$ points per degree [38]. In other words, the derivative of $Q_{i,k}$ with respect to $d$ should be zero given any rate when $d$ is so large that the angular resolution $f_{ang}$ reaches $60/^{\circ}$:

The derivative goes to zero when $f_{ang}$ is $60/^{\circ}$ if $c=\frac{e}{60}$.

Then we can get the curve similar to the one in [8]. Taking a tile for example, the utility curve with respect to tile rate and distance is shown in Fig. 4. It’s a tile from point cloud video Long Dress of 8i [15], where the figure is $1.8m$ high and tile is at the 4th level of the whole octree. For more details about the dataset, please refer to Section V. For simplicity, we ignore the subscripts of $Q_{i,k}$ as $Q$ in the following sections.

We now develop an analytical algorithm for solving the utility maximization problem formulated in Sec. IV-B. In Equation (IV-B), the second term $Q\left(\sum_{j=i+1}^{I}r_{j}(\tau+i,k),\tilde{d}_{\tau+i,k}\right)$ represents the tile quality of the layers that have been downloaded to the buffer before the current round, which is a given constant for the rate optimization at the current round. The utility maximization problem for each round is simplified as below, along with the constraints:

where $T$ is the video length, and $R(\tau+i,k)$ is the maximum rate of each tile $(\tau+i,k)$. The tile rate allocation problem is similar to the typical water-filling problem, where we “fill” the tiles in an optimal order based on their significance determined by the existing rates, probability to be viewed, distance from the viewer, and the calibration weights $\{w_{i}\}$.

Equation (4) is a nonlinear optimization problem so that the Karush–Kuhn–Tucker (KKT) conditions serve as the first-order necessary conditions. Furthermore, the KKT conditions for this problem are also sufficient due to the fact that the tile utility model $Q(r,d)$ is concave in terms of $r$ with a given $d$, and the inequality constraints (4b) and (4) are continuously differentiable and convex, and (4d) is an affine function. Therefore, we apply KKT conditions to optimally solve this tile rate allocation problem as shown in Algorithm 1. And the detailed KKT condition-based optimization is explained in Section IV-E.

In this section, we explain how to embed KKT condition-based optimization into Problem 4. We follow the standard procedures of KKT conditions.

1. 1.

   Non-progressive Downloading: This baseline is similar to the traditional video streaming in 2D video with one new segment downloaded to the end of the streaming buffer in each round. The rate allocation between frames within each new segment is optimized using a KKT algorithm similar to Algorithm 1 and 2, based on just one-time FoV prediction result.

2. 2.

   Progressive with Equal-allocation: To demonstrate the effectiveness of KKT based optimization approach for progressive streaming, we evaluate a naive progressive streaming baseline where the available bandwidth is equally allocated over all active tiles falling into the predicted FoV at each round.

3. 3.

   Rate-Utility Maximization Algorithm (RUMA): In the related state-of-the-art work [7], the authors proposed a tile utility model where the tile utility is simply the logarithm of the tile rate multiplied by the number of differentiable points. Based on this model, the authors further proposed a greedy heuristic tile rate allocation algorithm which we call RUMA for short. RUMA didn’t explicitly introduce the concept of scalable PCV coding. Different from RUMA, in our work, we formulate the PCV streaming problem with a well developed concept of scalable coding, and propose a more refined utility model that better reflect viewer’s visual experience when viewing a point cloud tile from certain distance. To achieve this, we have coded several test PCVs using MPEG G-PCC and found that the level of detail (LoD) is logarithmically related to the rate. Due to tile diversity, the data rate needed to code octree nodes up to level $H$ is highly tile-dependent. In other words, given a coding rate budget $r$, the achievable LoD is tile-dependent. We fit the coefficients of this logarithmic mapping from rate to LoD, and model the tile utility as a function of the angular resolution to replicate the empirical subjective utility-(rate, distance) curve in [8], which makes our utility model more convincing. Also, we adopt KKT to solve the continuous version of the rate allocation problem then round the rate to its discrete version. We show through simulation experiments that our method outperforms RUMA.

We run simulations with real users’ FoV traces [15] over four 8i videos. The height of the point cloud cube is $1.8m$ and roots of tiles are at $4th$ level of the whole octree. Each tile subtree has 6 different levels of detail. The update window size is $I=20s$, and it moves forward every one second. We are using $10$ FoV traces and $3$ bandwidth traces, and the quality results are averaged over frames in Table III and IV.

Table III and IV display mean and variance of different metrics in different scenarios. When both the bandwidth and the FoV oracles are available (Scenario A), non-progressive streaming is comparable with progressive streaming. But in the realistic setting with network bandwidth estimation errors and FoV prediction errors (Scenario B), our proposed progressive streaming solution with either constant or exponentially decreasing frame weights can deliver much higher quality in most cases, measured using both the quality per degree and the delivered angular resolution or the number of points per viewing degree, averaged over all FoV tiles.

We believe that in addition to the average results from Table III and IV, it’s also very important to show the frame quality evolution across time in specific streaming sessions in Fig. 5 and Fig. 6 to demonstrate the drawback of non-progressive baseline as well as the superiority of progressive downloading due to its multi-round downloading with more and more accurate FoV prediction for every frame. In the following sections, we show the comparison results in real-world Scenatio B only. In Section V-C1, we show results for each of the four 8i videos, while the rest of the sections only present the detailed results for Long Dress because all the other videos have similar trends.