Point Cloud Compression using Depth Maps
In this paper we investigate the usage of depth maps as a structure to represent a point cloud.The main idea is that depth maps implicitly define a global manifold structure for the underlying surface of a point cloud. Thus, it is possible to only work on the parameter domain, and modify indirectly the point cloud. We show that this approach simplifies local computations on the point cloud and allows using standard image processing algorithms to interact with the point cloud. We present results of the application of standard image compression algorithms applied on depth maps to compress a point cloud, and compare them with state ofthe art techniques in point cloud compression. We also present a method to visualize point clouds in a progressive manner, using a multiresolution analysis of depth maps. Introduction 3D data acquisition has been an active research field over the last years. High resolution devices are able to acquire scenes composed of billions of points. Clouds of points are often transformed in polygon meshes, one of the most popular representation for 3D models. In particular triangle meshes, simple, flexible and widely supported by graphics hardware. With high resolution acquisitions, the resulting meshes are huge. The handling and common processings such as transmission or visualization become complex, or just impossible, even with workstations. Therefore in many industrial domains, visualizing point clouds directly becomes common, and the compression of such data has been an active field of research for one decade. Our current work focuses on the transmission and the visualization of massive point clouds on different types of devices (computers, tablets, smartphones. The key problem is to adapt the quantity of information to transmit and/or display, in function of the performances of the user devices and the bandwidth limitations. In this context, data compression is a well suited tool. The problem with point clouds is that they are not structured and have no topology. They are difficult to handle, because of the lack of connectivity information. Even the basic notion of neighborhood for a point is problematic. Therefore all the prior methods of compression for point clouds build their own structure before encoding [11, 2, 13, 4, 5, 15, 8] However, this regularity exists natively in the data generated by multiple 3D acquisition devices, namely depth maps. A depth map is a grayscale 2D image, representing the distance from each sample to the scanning device during an acquisition. Every nonblack pixel is representing a point in the scene captured (black pixels representing the background) A point is defined by its 3D coordinates {x,y,z} In a depth map, a pixel is defined by one single coordinate {d} the distance from the camera. Indeed, the image is sampled on a regular lattice, the coordinates {i, j} of the pixel in the image are implicit, and do not need to be stored. To project points from the map to the 3D space, one matrix is needed for each depth map (16 real numbers) Its cost is negligible, in comparison with the map cost. Thus, depth maps are naturally more compact than point clouds, as long as 1 3 of the total number of pixels represent points in R 3. Depth maps do not provide only geometric information. They also define a parameterization domain and a segmentation related to the different points of view (position and orientation of the system during acquisition) So numerous techniques of image processing can be used to process the associate point clouds. Moreover, their regular lattice enables efficient wavelet filtering, as in the classical 2D image domain. Considering these nice properties, we choose to investigate the use of depth maps as an alternative representation of point clouds, and aim to develop algorithms based on this specific structure. In this paper, we present our preliminary works in the context of visualization, and of compression. The rest of the paper is organized as follows. We first present some recent methods of compression for point clouds. The following section explains how a set of depth maps can be used as a parameterization domain for point clouds. Then, we present two scenarios where image based algorithms can be used to process point clouds easily. First, we show how multiresolution analysis of a set of depth maps enables LOD and view dependent visualization of point clouds. Second, we explore the use of image coders to compress a point cloud, by compressing its associated set of depth maps. In particular, we compare the RD (Rate Distortion) performances of several image coders and of one state of the art point cloud compression method. State of the art As introduced before, a point cloud is only a set of samples distributed in a 3D space. It has no structure, no topology. Therefore, in the domain of compression, all the recent methods use a multiscale structure to represent a point cloud before encoding it. Sphere hierarchy In 2000, the authors of [11] suggest to handle massive datasets by using a bounding sphere hierarchy. Then, each sphere encodes its position relatively to its parent sphere. Octree based methods In 2002, the authors of [2] propose to use a high resolution voxel grid, and to progressively coarsen it by merging 8 (2x2x2) blocks. To reconstruct the initial resolution grid, one byte is used to select which ones of the 8 merged blocks contain points. Later, [13] and [4] present similar methods that embedd the point cloud in an octree. The bounding box of a point cloud is recursively subdivided, and each cell is encoded with a prediction scheme depending on the configuration of the children cells. Incremental simplification In 2004, a progressive decimation scheme for point clouds is proposed by [15] Pairs of points are merged recursively, and a prediction scheme encodes the position of merged points. Segmentation based methods The same year, an original approach is proposed in [8] The authors develop a method that segments a point cloud in several subsets, such as each subset can be parameterized by a height field. Hence, any still image compression scheme can be used to encode these 2D data. Theoretical foundations The link between a point cloud defining a surface in 3D space, and a depth map is given by a projection matrix M. For each point v R3, it computes p R2, the position of the projection of v in a depth map. This transformation is invertible (M is an upper triangular matrix, with non zero coefficients on the diagonal) and enables the embedding of 2D pixels in 3D space. The surface constructed by the embedding of every point of a depth map is called a range surface. This projection procedure is equivalent to the notion of parameterization in differential geometry. A range surface Sk corresponds to a patch Ck R3 and a projection matrix Mk represents a parameterization function phk, linking a patch Ck to a parameterization domain Ok R2 (representing a depth map) Transition functions tphi ph j define the link between parametric coordinates of points belonging to a common intersection between two patches Ci and C j v CiC j, ph j(v) tphi ph j (phi(v) (1) which is equivalent to v SiS j, M j v M j *M 1 i (Mi v) (2) Figure 1. Set of overlapping parameterizations (phi and ph j) connected by transition functions tphi ph j [10] Given this link, we can consider a point cloud as simply being an embedding of a set of depth maps and storing only these ones in memory. This allows working in the parameterized domain to interact with point clouds, as done in [8] for compression, or [9] for spectral processing. Visualization As introduced before, visualizing a point cloud using depth maps is not more complex than visualizing the raw point cloud. When rendering a model, points are projected on the screen and become pixels. This is done by applying a matrix transform to all points of the model, which will compute their position in the rendered view. When rendering a point cloud from a set of depth maps, only one additional step is needed to rebuild the point cloud: the embedding of the pixels in R3. Considering that, we only keep depth maps and projection matrices in memory, instead of a set of 3D positions. In this part we show how we can represent a point cloud progressively by applying a multiresolution analysis on each depth map. Multiresolution analysis The wavelet transform [7] is a time frequency transformation, decomposing a signal l0 in a "low frequency" signal l 1, approximating the original signal (average subsampling) a set of wavelet coefficients g 1, representing the "highfrequency" details removed to get the "low frequency" signal. This decomposition step is called analysis. It is an invertible operation, allowing the perfect reconstruction of the original signal. The inverse operation is called synthesis. In the case of images, a dyadic decomposition is often applied: only the lowfrequency signal is decomposed at each level of resolution. This representation is relevant for transmitting an image progressively: a coarse version is first sent, and then the sets of coefficients are sent to reconstruct the original image progressively. To perform a multiresolution analysis, we use a lifting scheme, which is an efficient implementation of the wavelet transform [14] The lifting scheme is composed of 3 different steps: Separation. A signal li is decomposed in two subsets li 1 and gi 1 gathering respectively the even and odd samples (pixels in the case of an image) of the original signal; Predict. Odd samples values gi 1 are predicted using an operator P from the values of li 1. Prediction errors represent wavelet coefficients and are stored in gi 1; Update. Values of li 1 are updated using an operator U based on the wavelet coefficients gi 1 obtained. One advantage of the lifting scheme is to obtain the inverse transform just by applying the preceding steps in the inverse order. This process is gener
3D Image Processing, Measurement and Applications