Xin Su

Thomas Maugey

Christine Guillemot

Rate-Distortion Optimized Graph-Based Representation for Multiview Images with Complex Camera Configurations

Rate-Distortion Optimized Graph-Based Representation for Multiview Images with Complex Camera Configurations

Xin Su, Thomas Maugey Member, IEEE and Christine Guillemot Fellow, IEEE Abstract-Graph-Based Representation (GBR) has recently been proposed for describing color and geometry of multiview video content. The graph vertices represent the color information, while the edges represent the geometry information, i.e. the disparity, by connecting corresponding pixels in two camera views. In this paper, we generalize the GBR to multiview images with complex camera configurations. Compared with the existing GBR, the proposed representation can handle not only horizontal displacements of the cameras but also forward/backward translations, rotations, etc. However, contrary to the usual disparity that is a 2-dimensional vector (denoting horizontal and vertical displacements), each edge in GBR is represented by a onedimensional disparity. This quantity can be seen as the disparity along an epipolar segment. In order to have a sparse (i.e., easy to code) graph structure, we propose a rate-distortion model to select the most meaningful edges. Hence the graph is constructed with "just enough" information for rendering the given predicted view. The experiments show that the proposed GBR allows high reconstruction quality with lower or equivalent coding rate compared with traditional depth-based representations.

Index Terms-Geometry information, graph-based representation (GBR), complex camera configurations, disparity, distortion model

I. INTRODUCTION

T HE recent and upcoming imaging and display hardware encourage the development of new multiview video coding approaches, such as 3DTV and free viewpoint TV [START_REF] Tanimoto | Free viewpoint television (FTV)[END_REF]. The very large volume of data requires the use of a proper representation of the data, compact and efficiently compressed. Basically, a representation of multiview data should capture both color and geometry contained in the 3D signal. The color information is typically described by 2D images. The scene geometry information can be explicitly represented by depth or disparity [START_REF] Shum | Survey of image-based representations and compression techniques[END_REF], [START_REF] Müller | 3-D video representation using depth maps[END_REF]. In order to construct a compact representation of multiview data, inter-view redundancy must be removed with the help of scene geometry given by the depth or disparity maps. The captured geometry information depends on the camera configurations. If the cameras are assumed to be aligned, as in conventional 3DTV applications, the displacement of the projection of one scene point from one view to the other is horizontal. For other applications such as free viewpoint television [START_REF] Tanimoto | Free viewpoint television (FTV)[END_REF], virtual reality [START_REF] Wexelblat | Virtual reality: applications and explorations[END_REF] or augmented Xin Su is with the Institut National de Recherche en Informatique et en Automatique, Rennes 35042, France (e-mail: xin.su@inria.fr).

Thomas Maugey is with the Institut National de Recherche en Informatique et en Automatique, Rennes 35042, France (e-mail: thomas.maugey@inria.fr).

Christine Guillemot is with the Institut National de Recherche en Informatique et en Automatique, Rennes 35042, France (e-mail: christine.guillemot.fr).

reality [START_REF] Azuma | A survey of augmented reality[END_REF], the camera configurations, hence the displacement of scene points from one view to the other, is more complex. In this paper, we focus on the problem of geometry compact representation with complex camera configurations.

In the popular multi-view plus depth (MVD) [START_REF] Merkle | Multi-view video plus depth representation and coding[END_REF] format, the geometry is represented by a depth map, a gray scale image describing the distance between the camera and the scene. The depth map is used by image-based rendering techniques to render virtual views at any viewpoint [START_REF] Martinian | View synthesis for multiview video compression[END_REF]. Lossy compressions of MVD format is classically performed by the high efficiency video coding standard, namely 3D-HEVC [START_REF] Müller | 3D high-efficiency video coding for multi-view video and depth data[END_REF], [START_REF] Tech | Overview of the multiview and 3D extensions of high efficiency video coding[END_REF]. However, the lossy compression of depth data may cause edge displacement artifacts around foreground objects in the rendered views due to the smoothing of depth edges. As shown in [START_REF] Bosc | Bitrate allocation for multi-view video plus depth[END_REF], depending on the camera acquiring configuration, a different ratio between depth and color bitrate may be needed.

To solve this problem, rate-distortion models (e.g., in [START_REF] Yuan | A novel distortion model and Lagrangian multiplier for depth maps coding[END_REF]) have been proposed to guarantee less depth error around edges. Another approach has been proposed in [START_REF] Gautier | Efficient depth map compression based on lossless edge coding and diffusion[END_REF] in which depth edges are losslessly encoded in order to keep the piecewise contour aspect of the depth images.

Disparity, as an alternative to depth, describes the scene geometry by the distance between two pixels representing the same 3D point in two different views. Compared with the depth that gives an exhaustive representation of the geometry with respect to a single viewpoint, the disparity represents the geometry relation between two views. Based on the camera parameters of the two views, the disparity in each point can be easily derived from the depth information. In multiview video coding (MVC) [START_REF] Vetro | Overview of the stereo and multiview video coding extensions of the H. 264/MPEG-4 AVC standard[END_REF], the disparity is used for interview prediction, but its "block similarity" assumption may fail when the foreground color is similar to the background color or when homographic transforward occurs between the two views. More recently, a graph-based representation (GBR) [START_REF] Maugey | Graph-based representation for multiview image geometry[END_REF] has been proposed, in which, the graph connections are derived from the disparity and hold pixel-based "just enough" geometry information to synthesize the considered predicted views. However, only horizontal translations of the cameras were considered in the GBR proposed in [START_REF] Maugey | Graph-based representation for multiview image geometry[END_REF].

In this paper, we extend the promising GBR approach to multiview systems with complex camera configurations. Beyond horizontal camera translations, the proposed GBR can handle more complex camera displacements, such as rotations and forward/backward translations. In the former GBR, the edges describe the disparity as follows. Each inter-view edge of the graph links one pixel and its (horizontal) neighboring pixel in the 3D scene (the gap between the two pixels is the disparity). The extension to complex camera configurations is not straightforward since the disparity becomes two-dimensional (horizontal and vertical displacement). As it was preliminary studied in [START_REF] Su | Graph-based representation for multiview images with complex camera configurations[END_REF], in order to circumvent this complexification, we use the concept of epipolar segment to keep the disparity one-dimensional. An epipolar segment (the purple segment shown in Fig. 1) is a line segment consisting of all possible projections of a pixel with varying depth. A onedimensional quantity is enough to denote the true projection position on the epipolar segment. Thus, in the proposed GBR the edge (e.g., the blue link in Fig. 1) representing the disparity can be presented by a one-dimensional value. This onedimensional value, namely unidimensional disparity in this paper, can be seen as the disparity on the epipolar segment.

In order to have a sparse (i.e., easy to code) graph structure, we horizontally group neighboring pixels to form a segment and only one connection is assigned to this segment, instead of one connection per pixel. Moreover, a rate-distortion model taking into account the reconstruction quality and the bitrate needed for coding the geometry is used to remove the less important edges of the graph and regroup a larger set of pixels described by the same edge. The proposed rate-distortion model minimizes a cost function consisting of distortion and bitrate. The constructed graph edges are finally represented by the unidimensional disparity maps. To code the unidimensional disparity maps, we first propose a lossless compression scheme using the mix of JBIG [START_REF] Martins | Lossy/lossless coding of bi-level images[END_REF] and arithmetic edge coding [START_REF] Daribo | Arbitrarily shaped motion prediction for depth video compression using arithmetic edge coding[END_REF] for the position of non-zero values in unidimensional disparity maps and DPCM for the unidimensional disparity values. A lossy compression with HEVC of the unidimensional disparity maps has also been considered to further reduce the bitrate. Our experimental results demonstrate that the proposed GBR leads to high reconstructing quality with less or comparable coding rate compared with traditional depth-based representations.

The proposed GBR can be considered as a lossy representation followed by a lossless compression of multiview geometry, compared with state of art depth-based approaches which are a lossless representation followed by a lossy compression. Since the edges of the constructed graph connect pixels across the views, providing more neighboring (inter views) information than typical 2D images, new compression approaches based on graph transform [START_REF] Maugey | Luminance coding in graph-based representation of multiview images[END_REF] may be developed based on the GBR structure for coding the pixels color values, which is out of the scope of this paper.

The rest of this paper is organized as follows. In Section II, we discuss related work. In Section III, the construction of graph is introduced in detail. Section IV presents the proposed rate-distortion model that selects the most meaningful edges of the graph. The view reconstruction from a graph is detailed in Section V. Finally, in Section VI, we show the experiments conducted to compare depth-based representations and our GBR.

II. MULTIVIEW GEOMETRY AND VIEW SYNTHESIS A. Depth Image Based Rendering (DIBR)

Let us consider a scene captured by two cameras views I 1 and I 2 of size X × Y with camera configurations Φ 1 and Φ 2 , where Φ i = {M i , R i , T i } are the parameters of the camera. M i is the intrinsic matrix, R i is the rotation matrix and T i is the position of the camera ([R i | -R i T i ] is also known as the extrinsic matrix). As detailed in [START_REF] Martinian | View synthesis for multiview video compression[END_REF] and illustrated in Fig. 1, pixel (x, y) in I 2 (with depth z 2 (x, y)) can be projected to

I 1 by                  x r y r z r   = R -1 2 M -1 2   xz 2 (x, y) yz 2 (x, y) z 2 (x, y)   + T 2   x ′ z 1 (x ′ , y ′ ) y ′ z 1 (x ′ , y ′ ) z 1 (x ′ , y ′ )   = M 1 R 1     x r y r z r   -T 1   , (1)
where, [x r , y r , z r ] T are the coordinates of the corresponding point in the 3D scene. The relation between pixel (x, y) in I 2 and pixel (x ′ , y ′ ) in I 1 can be denoted as [x, y, z 2 (x, y)] T

Φ1,Φ2

[x ′ , y ′ , z 1 (x ′ , y ′ )] T , which means they satisfy Eq. [START_REF] Tanimoto | Free viewpoint television (FTV)[END_REF]. Under the Lambertian assumption, the color at (x, y) in I 2 is the same as the color at (x ′ , y ′ ) in I 1 .

Considering I 1 as the reference view (the color and depth are known), the predicted view (I 2 ) can be generated by Eq.(1) from the reference view. This is referred to as forward projection (or forward warping), which is classically used in depth-image-based rendering (DIBR).

B. Depth vs. Disparity

A depth value is the distance from the observed object to one camera, while disparity is the displacement of pixels between two cameras. The position of the projected point (x ′ , y ′ ) in I 1 of a pixel (x, y) in I 2 corresponding to a 3D point of depth z 2 (x, y) is given by Eq.(1). The disparity is thus defined as

⃗ d(x, y) = (∆x, ∆y) = (x ′ -x, y ′ -y) , (2)
where ∆x, ∆y ∈ R. When the displacement of the camera from one view to the other is a horizontal translation, the geometrical correlation between two views is only horizontal. In this case, the disparity vector ⃗ d(x, y) = (∆x, ∆y = 0) is simplified to a real number d(x, y) = ∆x. Note that the coordinates (x, y) in Eq.( 1) are integer numbers, while the coordinates (x ′ , y ′ ) (the projection position) are not integer. However, for the sake of simplicity, the coordinates (x ′ , y ′ ) are often rounded to the nearest integer in the literature. In this paper, the geometry is represented by a position on a 1D epipolar segment and not in the image plane. Therefore, the disparity presented by the position can provide subpixel precision, which is not integer value commonly used in disparity based representation. This 1D disparity measure is further explained in the sequel.

We see here that the fundamental difference between depth and disparity resides in the fact that disparity corresponds to two cameras, while depth to only one of them. Compared with depth-based representations, the GBR representation introduced in this paper, as well as the disparity and former GBR, simplifies the depth by considering the predicted views. Moreover, the proposed GBR uses the concept of epipolar segment to keep the disparity unidimensional even for complex camera configurations.

III. EXTENSIONS OF GBR

Fig. 2.a shows a set of multiview images. Among them I 1 is used as reference and I 2 and I ′ 2 are predicted. The camera displacement from I 1 to I 2 is only a horizontal translation, while the displacement from I 1 to I ′ 2 is horizontal translation and rotation. An illustration of the former GBR [START_REF] Maugey | Graph-based representation for multiview image geometry[END_REF] of one row in I 1 and I 2 is shown in Fig. 2.b. The principle of the graph edges is connecting pixels and their neighboring pixels in the 3D scene. Since the camera displacement is simple (only horizontal), the pixel displacement has only horizontal component. Each row in I 2 can be recovered from the same row in I 1 by copying color values pixel by pixel from left to right and following the graph edges.

When the camera displacement becomes complex, for instance from I 1 to I ′ 2 , a naive extension of the former GBR can be constructed but with dense edges, as shown in Fig. 2.c. This is because for pixels in one row of I 1 , their corresponding pixels (corresponding to the same points in the 3D real world) in I ′ 2 are no longer located at the same row due to the complex camera configurations. More edges are thus needed to reconstruct the rows of I ′ 2 . To reduce the graph density in the complex camera configuration cases, a different principle for graph edges is proposed in this paper. As shown in Fig. 2, the idea consists in connecting pairs of straight segments across two views. The predicted view can be reconstructed segment by segment still following the graph edges. The interest of the proposed GBR is that the sparsity of the edges is of a similar order than the previous GBR, even when the camera displacement is complex. An earlier version of this new graph construction is presented in [START_REF] Su | Graph-based representation for multiview images with complex camera configurations[END_REF]. However, the graph in [START_REF] Su | Graph-based representation for multiview images with complex camera configurations[END_REF] is constructed only for the 2 input views with regards to the distortion of rendering results, instead of the rate-distortion model proposed in this paper. The proposed GBR in this paper can easily handle multiple views representation and virtual synthesis tasks.

IV. GBR REPRESENTATION This section details how to construct a graph for multiview images and how to reconstruct views from the graph.

A. Graph Construction

Let us denote the constructed graph by G = {V, E}, where vertices V = {v i } (∀i = 1, . . . , N XY ) correspond to the pixels in multiview images {I n } n=1,...,N , and edges E = {e ij } (i, j = 1, . . . , N XY ) connect pairs of pixels across two views.

1) Graph for two views: As mentioned before, pixels in I 1 (reference view) are grouped into a set of straight horizontal segments. Pixels in each segment are supposed to have the same depth. For instance, as shown in Fig. 2.d, pixels in one row of I 1 are grouped into 3 segments. Note that we can select the straight segments horizontally (row by row), or vertically (column by column) or in zigzag order. However, since the cameras are usually placed horizontally and camera rotations are also in a horizontal plane, we thus form the straight segments horizontally. Each segment in I 1 is linked to another segment in I 2 by an edge of the graph, i.e., the first pixels of the two segments are connected to each other, as shown in Fig. 3. The two linked segments correspond to the same segment in the 3D real world. The link, i.e., the graph edge, thus describes the disparity of the segment for two camera views. Since the depth of the segment can be estimated from the edge by Eq.( 1), one segment in I 1 needs only one edge to locate its corresponding segment in I 2 . The proposed GBR results in an edge set that only connects the pixels in two different views. Fig. 2.d gives an illustration of the edges of the constructed graph between two views.

2) Graph for multiple views: Given multiple views (more than 2 views), the graph construction is repeat from one view to another. As shown in Fig. 3, each straight segment in I 1 is connected to its corresponding segments in all other views. Using Eq.( 1) with camera parameters, the positions of these corresponding segments (in different views ) can be estimated from each other. Thus, in the constructed graph, only the graph edges between I 1 and I 2 are kept (marked by solid lines in Fig. 3), while the edges linked to other views I 3 , • • • , I N are redundant and can be removed (marked by dotted lines in Fig. 3).

3) Graph for disoccluded pixels: The disoccluded pixels in

I n (2 ≤ n ≤ N -1) are pixels not visible in I 1 , • • • , I n-1 , but first visible in I n .
The proposed GBR thus also builds edges for these disoccluded pixels. Similar to pixels in reference view I 1 , disoccluded pixels are grouped into straight segments according to their depth and one segment has one edge. Only edges linked to I n+1 are kept. The color of disoccluded pixels of I n are also stored in the vertices of the graph and used to render the following views I n+1 , • • • , I N . In other words, the disoccluded pixels in I n is treated as "reference pixels" for

I n+1 , • • • , I N .

B. Graph Description (unidimensional disparity description for edges)

Basically, the graph constructed in section IV-A captures both vertices V (corresponding to the color information of multiview images) and edges E (corresponding to the disparity of multiview images) of the graph. Since the compression of color information is out of the scope of this paper, no compression has been applied on the graph vertices V. The graph only represents the vertices corresponding to I 1 and the disocclusion pixels in I 2 , • • • , I N . The color information of the other pixels can be recovered from these vertices. Fig. 4.a gives an illustration of the constructed graph for a real dataset (Tsukuba dataset [START_REF] Peris | New Tsukuba Stereo Dataset[END_REF]), in which the red lines are the edges. As explained in the previous section, the edges for reference view (between I 1 and I 2 ) or for disoccluded pixels of I n (between I n and I n+1 ) can be described by a huge binary matrix of size 2XY × 2XY , which is a connectivity matrix between the 2XY pixels. However, since the edges link pixels across two views, the edges can be represented by The unidimensional disparity d (u) is the disparity on the epipolar segment, which can be seen as an index denoting the true projection position on the epipolar segment. a binary matrix of size XY ×XY . For each pixel in I n , all its possible projections (with varying depth) in I n+1 are located on an epipolar segment, as shown in Fig. 5. In addition, the true projection (x ′ , y ′ ) in I n is between the boundary projections (x ′ min , y ′ min ) and (x ′ max , y ′ max ), where projection (x ′ min , y ′ min ) is located by Eq.( 1) using the minimum depth and projection (x ′ max , y ′ max ) is related to the maximum depth. Therefore, a real number is enough to denote the projection position, e.g. the distance between (x ′ min , y ′ min ) and (x ′ , y ′ ). Thus, a new quantity d (u) n (x, y) named unidimensional disparity denoting the graph edge linking pixel (x, y) in I n and position (x ′ , y ′ ) in I n+1 is given by

d (u) n (x, y) = { 0, if pixel (x, y) has no edge round ( | ⃗ d(x,y)| | ⃗ dmax(x,y)| W + 0.5 ) , otherwise , (3)
where,

| ⃗ d(x, y)| | ⃗ d max (x, y)| = √ (x ′ min -x ′ ) 2 + (y ′ min -y ′ ) 2 √ (x ′ min -x ′ max ) 2 + (y ′ min -y ′ max ) 2 . ( 4
)
By using the unidimensional disparity, the connectivity matrix can be replaced by a smaller binary matrix with size of W × XY , where W is the maximum quantization bins within the epipolar segment. Since d (u) measures the distance between (x ′ min , y ′ min ) and (x ′ , y ′ ), it can be considered as a disparity along the epipolar segment.

Fig. 4.b gives an illustration of unidimensional disparity in the toy example. Each pixel (black stars) in I 1 can be projected to I 2 with varying depth. These projections are located on the white lines in I 2 , which are the epipolar segments. The unidimensional disparity d (u) denotes the location of the true projection along the epipolar segment with respect to the position (x ′ min , y ′ min ) corresponding to the projection of the pixel (x, y) assuming the minimum depth value.

C. View Reconstruction from a Graph

The pixels in the reference view I 1 and the disoccluded pixels in I n are recovered directly by copying the color from the corresponding vertices of the graph. The reconstruction of the remaining pixels in I n (2 ≤ n ≤ N ) relies on the following steps. Fig. 6. Mesh based rendering. On the left, Every 3 neighboring pixels with the same or similar depth form a triangle mesh. On the right, the triangle mesh is projected to other views by Eq.( 1) with estimated depth. The color values of the pixels inside the projected triangle mesh are the weighted mean of the color values of the triangle mesh's three vertices.

• Graph edge → depth: The depth of each segment is estimated from the edge on the segment by Eq.( 1). • Mesh based projection [START_REF] Muddala | Free View Rendering for 3D Video[END_REF]: Each segment and its neighbor segments in previous row can form some triangle meshes, as shown in the left image of Fig. 6. The 3 vertices (pixels) of one triangle mesh have the same or similar depth, which means the 3 pixels belong to the same object. The triangle mesh is projected to other views by Eq.( 1) with estimated depth, as shown in the right of Fig. 6. • Color interpolation: The color values of pixels located in the projected triangle mesh, i.e., the red pixels in Fig. 6, are the weighted mean of the color values of the triangle's three vertices. Let us assume that pixel (x ′ , y ′ ) is located inside the triangle mesh with vertices at (x ′ 1 , y ′ 1 ), (x ′ 2 , y ′ 2 ) and (x ′ 3 , y ′ 3 ). The color at position (x ′ , y ′ ) can be calculated as

I(x ′ , y ′ ) = ω 1 ω I(x ′ 1 , y ′ 1 ) + ω 2 ω I(x ′ 2 , y ′ 2 ) + ω 3 ω I(x ′ 3 , y ′ 3 ) , (5)
where

ω j = exp ( -(x ′ -x ′ j ) 2 -(y ′ -y ′ j ) 2 ) , ω = ω 1 + ω 2 + ω 3 . (6)

D. Virtual view Synthesis by the Graph

Although it is not the core purpose of the proposed GBR, the geometry described by the graph edges can be used to synthesize virtual views. The depth of reference view is first estimated from the graph edges. Virtual views thus can be synthesized with the estimated depth. However, the graph is constructed with the input of multiple views instead of the virtual views, especially the graph is sparsified and optimized to render the input of multiple views (detailed in section V). The rendering quality of the virtual viewpoints by the graph thus may be not as good as when using depth based representation.

V. GRAPH SPARSIFICATION

According to the GBR's principles presented in section IV, pixels on each segment have the same depth. In order to sparsify the graph, i.e., reducing the number of edges, we can group pixels even if their depth are not exactly equal. The segment depth can thus vary within a range [z -∆z, z + ∆z] (∆z ≥ 0). It is obvious that large ∆z leads to an inaccurate geometry, which further leads to a low rendering quality but leads to a graph less costly to code. Instead of having a predefined ∆z, we adapt it to the encoding bitrate and rendering quality.

A. Graph Coding 1) AEC-based coding:

In this paper, we only consider the geometry bitrate. The edges of the graph have been described by d (u) maps (a toy example shown in Fig. 4.b and c). Each view I n (1 ≤ n < N ) has a d (u) map (note that for d (u) maps of predicted views I 2 , • • • , I N -1 , the non-zeros values are only located in the disoccluded regions). Fig. 7.b is a real d (u) map, in which pixels with edges are shown in non-white color (different grays show different d (u) values). Comparing Fig. 7.a and b, we can see that the contours in the d (u) map correspond to the contours in color image. It is natural that a new segment appears with an edge in the graph when the depth is discontinuous. We thus encode the d (u) map contour by contour. Let us assume that the corresponding d (u) map of I n consists of P contours {C n (p)}, ∀p = 1, . . . , P (i.e., continuous set of pixels with 1 pixel per segment). The encoding of each contour C n (p) proceeds as follows.

• First pixel location: The exact location of the first pixels of each contour is described by a bright point in a bi-level image, as shown in Fig. 7.c. This bi-level image is then encoded by JBIG (Joint Bi-level Image Experts Group) [START_REF] Martins | Lossy/lossless coding of bi-level images[END_REF]; • Direction stream {∆x}: The exact locations of other pixels (except first pixels) of C n (p) are encoded by the arithmetic edge coding (AEC) method [START_REF] Daribo | Arbitrarily shaped motion prediction for depth video compression using arithmetic edge coding[END_REF] (the direction stream in Fig. 7.c); • d (u) stream {d (u) (x,y

R(E) = N -1 ∑ n=1 P ∑ p=1 R(C n (p)) , ( 7
)
where C n (p) is the p-th contour in the d (u) map of view I n . The bitrate for encoding the contour

C p is R(C n (p)) = R J (C n (p)) + R D (C n (p)) + R V (C n (p))
First pixel Direction d (u) Value [START_REF] Müller | 3D high-efficiency video coding for multi-view video and depth data[END_REF] where,

R J (C n (p)) = c (bits) , 0 < c < 32 R D (C n (p)) = entropy({∆x}) , R V (C n (p)) = entropy({∆d (u) (x, y)}) . ( 9
)
R J is the bitrate for encoding the exact locations of first pixels of contour C n (p). Since the JBIG encoder has been applied, R J highly depends on the image content. However, for the sake of simplicity, we assume that R J is constant for each contour. This constant value c is between 0 and 32, where 32 is the maximum number of bits for coding the coordinates of one pixel (16 bits for x-coordinate and 16 bits for y-coordinate).

In this paper, we set c = 24. R D is the rest of the contour C n (p), which is measured by the entropy of the direction stream {∆x}. R V is the bitrate needed for encoding the d (u) values on the contour C n (p).

2) HEVC-based coding: AEC-based coding is a lossless compression of d (u) images (the edges of the graph). However, to further reduce the bitrate, we can compress the d (u) images with a lossy compression method, i.e., HEVC. Before being compressed by HEVC, the zero values in d (u) images are replaced by their left first non-zeros values to smooth the d (u) images. The filled d (u) images are seen as a video (I-P-P-P-• • • sequence) then compressed by HEVC.

B. Rate-Distortion model

In this paper, we measure the rendering quality by the color distortion of the predicted views:

D(E) = N ∑ n=2 Y ∑ y=1 X ∑ x=1 I n (x, y) -În (x, y) 2 2 , ( 10
)
where În (x, y) is the rendered color at position (x, y) in I n which depends on the graph edges, and I n (x, y) corresponds to the targeted color (e.g., the original color).

A Lagrangian rate-distortion optimization is performed searching to minimize the cost function Eq. [START_REF] Yuan | A novel distortion model and Lagrangian multiplier for depth maps coding[END_REF], where the bitrate R(E) given by Eq.( 7) and the distortion D(E) given by Eq. [START_REF] Bosc | Bitrate allocation for multi-view video plus depth[END_REF]. α is the Lagrangian multiplier which represents the relation between bitrate and rendering quality (distortion):

J = D(E) + αR(E) , ( 11
)
where J is the Lagrangian cost (smaller J values mean better optimal status). In this paper, we propose to simplify the graph by searching the set of edges which can be removed such that the Lagrangian cost function is minimized:

E = argmin E ′ J = argmin E ′ D(E) + αR(E) . ( 12
)
However, since the solution of Eq.( 12) is complex, we present two approximate minimizations in the following.

C. Row-wise minimization by shortest path algorithm

1) Row-wise rate-distortion model: Instead of carrying out a global minimization over the entire graph, we perform the minimization in Eq.( 12) row-wise as illustrated in Fig. 8. Taking the y-th row of view I n as an example, all the pixels are initially grouped into 5 segments based on their depth (pixels on each segment have the same depth). Then, some edges are removed (i.e., some segments are merged) if they reduce the row-wise rate-distortion cost function Eq.( 13):

J n (y) = N ∑ m=n+1 X ∑ x=1 D m (d (u) n (x, y)) +α R n (d (u) n (x, y)) , Distortion Bitrate (13)
where D(d (u) n (x, y)) is the distortion when projecting pixel (x, y) from the reference view I n to the other view I m (using mesh-based rendering). The bitrate term R(d (u) n (x, y)) is the bitrate of encoding d (u) n (x, y) in I n , which can be calculated as

R(d (u) n (x, y)) = R(C p+ ) -R(C p-), (14)
where pixel (x, y) is on contour C n (p). C n (p+) denotes the contour with pixel (x, y) (and pixel (x, y) is the end point of contour C n (p+), as shown in Fig. 8.a), while C n (p-) is the contour without pixel (x, y). The unidimensional disparity d (u) n in each position (x, y) of the y-th row in view I n is obtained by minimize the Lagrangian cost J n (y), i.e.,

{d (u) n (x, y)} = argmin {d (u) n (x,y)} J n (y) , ∀x = 1, . . . , X . ( 15
)
can be considered as an approximate minimization of Eq.( 12) (under the assumption that minJ ≈ ∑ n ∑ y minJ n (y)).

2) Minimization by shortest path algorithm:

The removing of one edge, i.e., merging one segment into its left segment, can be modeled as a shortest path problem. For instance in the example shown in Fig. 8.b, the path P 4,5 connects the beginning of segment 4 and the end of segment 5, and represents the fact of merging segments 4 and 5. Similarly, path P 1,5 denotes the merging of segments from 1 to 5. The cost of path P s,t (that segments from s to t are regrouped into one segment) is defined as

c s,t = N ∑ m=n+1 t end ∑ x=sstart D m (d (u) n (x, y)) + αR n (d (u) n (s start )) (16)
where s start is the first pixel of segment s and t end is the end of segment t. The optimal solution of the shortest path algorithm provides the shortest path from the end to the beginning of the y-th row of view I n .

VI. EXPERIMENTS

A. Experimental setup Data sets. In this section, we present experiments to evaluate the performance of the proposed GBR. Three data sets have been tested: 1) Tsukuba dataset [START_REF] Peris | Towards a simulation driven stereo vision system[END_REF]: Fig. 9.a is a 1 minute video sequence (1800 frames). Each frame contains a stereo pair with ground truth depth maps. Five frames of indices {1, 25, 50, 75, 100} have been selected as a set of multiview images. The first frame is reference view and the others are predicted views. 2) MSR dataset [START_REF] Zitnick | High-quality video view interpolation using a layered representation[END_REF]: the Ballet dataset is tested. The image of camera 4 is reference view (as shown in Fig. 9.b) and the image from camera 3∼0 are predicted views (totally 5 views). 3) Akko&kayo dataset [START_REF] Saito | Nagoya University Multi-view Sequences[END_REF] This paper only focuses on geometry information, the 2D image representing the color information of I 1 is assumed to have been transmitted separately. To assess the quality of the graph representation, the original (without compression) color information has been used. In addition, the color values of disoccluded pixels in predicted views are also transmitted separately.

Baseline methods. The proposed GBR is compared with traditional depth-based approaches, in which the depth maps are compressed by HEVC [START_REF] Sullivan | Overview of the high efficiency video coding (HEVC) standard[END_REF]. In these baseline methods, the DIBR [START_REF] Fehn | Depth-image-based rendering (DIBR), compression, and transmission for a new approach on 3D-TV[END_REF] method is applied to reconstruct the predicted views. Since the proposed GBR represents the geometry of both reference view I 1 and disocclusions of predicted views I n (2 ≤ n ≤ N -1), the depth maps of reference view I 1 and predicted views I n (2 ≤ n ≤ N -1) are compressed by HEVC as a video sequence.

Experiments. In section VI-B, we evaluate the capability of GBR to represent compactly a set of multiview image geometry. The PSNR values are computed over the whole multiview set using either the true original multiview images or the synthesized ones by DIBR with the reference view as reference. In section VI-C, even if this is not the main goal of GBR, we evaluate its ability to perform virtual view synthesis. In this case, the PSNR values are computed using the views rendered with original depth as reference signal.

B. Multiview representation 1) Parameter setting:

The Lagrangian multiplier α varies from 10 0 to 10 4 in the row-wise minimizations. In the HEVCbased graph compression, the QP parameter ranges from 0 to 51.

2) Results: We start by assessing the PSNR-rate performance of the multiview coding scheme based on the proposed GBR. Fig. 10.a shows the rate-distortion curves by GBR with AEC-based coding, GBR with HEVC-based coding and DIBR with depth compressed by HEVC. DIBR with non-compressed depth has also been tested as a baseline method, whose results can be seen as the maximum rendering quality since the non-compressed depth has been used. From the ratedistortion curves, we can see that the proposed GBR needs less bitrate to obtain the maximum PSNR (the one obtained by DIBR with non-compressed depth). Compared with GBR with AEC-based coding, GBR with HEVC-based coding costs less bitrate when achieving similar PSNR. In addition, GBR even yields the higher PSNR than the one obtained by DIBR+noncompressed depth. This is because sometimes removing an edge may have lower distortion than keeping it. And we use the real distortion in the Lagrangian rate-distortion cost instead of a model of distortion, which can help to remove these edges. This is further discussed in section VI-D. Fig. 11 illustrates the visual results of the reconstructed I 3 using different methods with similar bitrates. With similar cost in terms of bitrate, the visual results obtained with GBR usually are better than when using DIBR with HEVC (less artifacts on the edges of objects). However, we can notice that the rowwise minimization of GBR may introduce some artifacts in the regions with homogeneous depth, such as the displacement of the poster on the wall in Ballet dataset.

We then evaluate the PSNR-rate performance of the multiview representation with different original input views. We modified the multiview datasets as follows. The reference view I 1 is the same as in the experiment in Fig. 10 [START_REF] Oh | Depth map coding based on synthesized view distortion function[END_REF], [START_REF] Carballeira | Analysis of the depth-shift distortion as an estimator for view synthesis distortion[END_REF]. Fig. 10.b shows the rate-distortion performance. From these curves, we can find that at low bitrate our GBR is better than or comparable with HEVC, while at high bitrate HEVC generally outperforms our GBR. Compared with results in Fig. 10.a, results presented in Fig. 10.b only differs on the quality evaluation metric.

As we can see from Fig. 10, the PSNR-rate performance obtained by the GBR with AEC-based coding is always shown by "vertical" curves (the blue curves). This is because the lossless compression of AEC-based coding. It does not have too much compression techniques to reduce the bitrate, compared with the advanced and efficient (lossy) compression by HEVC-based coding (the red curves).

C. View synthesis

In some scenarios as FTV, the geometry information can be used to synthesize virtual viewpoints. It is well-known that the depth enables such efficient view synthesis tasks. While GBR's core purpose is to represent a set of input multiview images, the geometry described by the graph edges might be used to generate virtual views. This is what we study here. At the encoder, the GBR representation is constructed for some input multiple views. However, the viewpoints to be synthesized do not belong to the input multiview set. At the decoder, these virtual viewpoints can still be rendered from the constructed graph, as detailed in section IV-D. 1) Experiment setting: This experiment is tested on Tsukuba dataset. Since the multiview images are five frames {1, 25, 50, 75, 100} of 1 minute video, another three frames 60, 105 and 130 are tested as virtual views. The constructed graph in section VI-B is used here. These three virtual views (intermediate view, close virtual view and distant virtual view) are rendered with the constructed graph. Since the graph is constructed with (or is optimized to) the input multiple views, the rendering quality of these virtual viewpoints by the graph may depend on how close the virtual viewpoints and the input views are. More precisely, the intermediate view (frame 60) and the close virtual view (frame 105) are near the input multiple views, thus their rendered results with the graph are supposed to be comparable with or better than the ones obtained by depth based representation. While, for the distant virtual view (frame 130) which is far away from the input views, the rendered results by the graph should be worse than the ones obtained by depth based representation.

2) Results: The rendering results of the intermediate view (frame 60) and close virtual view (frame 105) are shown in Fig. 12.a and b, from which we can find that at low bitrate the proposed GBR is comparable with HEVC. However, since the graph is a simplified representation of depth with respect to the input views, it is not as good as depth (the full representation) when rendering virtual view, especially the complex ones, e.g., the virtual view (frame 130) shown in Fig. 12.c.

D. Analysis of GBR 1) Simplification of depth:

As introduced in section I, GBR simplifies the depth information so that it is sufficient to describe a given multiview set. Fig. 13 gives an illustration of how the proposed GBR adapts to the rendering difficulty. In this experiment, frame 100 in Tsukuba dataset is considered as the reference view. Three frames 1, 50 and 90 are considered as predicted views, for which the baseline with the reference view decreases. The geometry relation between the reference view and the predicted view becomes simpler. Theoretically, GBR needs to describe less geometry information to render frame 90 than for example rendering frame 1. Fig. 13.b-d show the d (u) images of the constructed graphs with different predicted views, frame 1, 50 and 90 respectively. These three d (u) images are obtained by row-wise minimization with the same parameter α, i.e., the same target quality. We can see that the d (u) image in Fig. 13.b becomes simpler (less graph edges) as long as the predicted view gets close to the reference view due to the proposed rate-distortion graph sparsification. It illustrates how the GBR adapts its amount of geometry depending on the rendering task.

2) Depth correction: As illustrated in the experiments in section VI-B, the proposed GBR can yield higher PSNR than the DIBR with original depth. This is because the depth images are not always accurate (e.g., estimated by block similarity of color images). Thanks to the graph sparsification, the proposed GBR can improve the depth by removing some noisy edges. For instance, Fig. 14 gives an illustration of depth correction done by the proposed GBR.

VII. CONCLUSION

In this paper, we have proposed an alternative to depth for multiview geometry representation. Contrary to the original GBR in [START_REF] Maugey | Graph-based representation for multiview image geometry[END_REF], the proposed GBR can deal with multiview images with complex camera configurations. A rate-distortion model has been proposed to simplify the graph. The proposed GBR representation simplifies the depth of multiview images for reconstructing the given predicted views, i.e., the GBR costs less bitrate when obtaining the same high rendering quality. Future work will focus on the full representation of both color and geometry, in which the connections of the graph should be used as a support for a better texture representation. The extensions of our GBR to other datasets, such as light fields (2D camera arrays), point cloud and so on, are also interesting challenges in the future.

Fig. 1 .

 1 Fig. 1. The concept of GBR: The vertices correspond to pixels of multiview images; The edges link pixels in one view and their projections in another view.

2 Fig. 2 .

 22 Fig. 2. GBR extensions to complex camera configuration. (a) Multiview images. From left to right and from top to bottom, the color images of I 1 , the depth of I 1 , the color images of I 2 and I ′ 2 . The camera displacements from I 1 to I 2 are only horizontal translations, while the displacements from I 1 to I ′ 2 are horizontal translations and rotations. In this example, I 1 is reference view, while I 2 or I ′ 2 is predicted view. (b) The former GBR [14] is constructed for I 1 and I 2 . The white pixels in I 2 are disocclusions while the white ones in I 1 are occlusions. Each row of I 2 can be reconstructed from I 1 by following the graph edges. Since the camera displacement is simple and the disparity is horizontal, the graph edges are sparse. (c) A naive extension of the former GBR for I 1 and I ′ 2 . I ′ 2 can be recovered from I 1 by following the graph edges, however since the camera displacements are complex (the disparity is two-dimensional), the graph edges are denser than the ones in (b). (d) The proposed extension of GBR for I 1 and I ′ 2 , in which the edges connect a pair of straight segments (across two views). The graph edges are as sparse as the simple case handled by the former GBR in (b).

Fig. 3 .

 3 Fig. 3. Graph for multiple views. Only the edges connecting reference view I 1 and I 2 are necessary, marked by solid line. Other edges connecting (marked by dotted lines) linked to view I 3 , • • • , I N can be estimated according the solid edges.

  (a) An example of the graph for two views. (b) The unidimensional disparity d (u) (c) The description of the graph.

Fig. 4 .

 4 Fig. 4. Graph construction and description for reference view I 1 (which is similar to the graph for disoccluded pixels of In). (a) An example of the graph for real dataset (Tsukuba dataset [19]). The red lines are the graph edges. (b) d (u) denotes the disparity along the epipolar segment (the white lines in I 1 ). It is the distance between the true projection and the boundary projection. (c) The graph is thus described by 2D color values on the graph vertices and a d (u) map describing graph edges.

Fig. 5 .

 5 Fig. 5.The unidimensional disparity d(u) is the disparity on the epipolar segment, which can be seen as an index denoting the true projection position on the epipolar segment.

  )}: Once the locations of C n (p) have been encoded, the d(u) values on C n (p) have also to be losslessly encoded from top to bottom (the d (u) stream in Fig.7.c). Note that we finally use a Differential Pulse Code Modulation (DPCM) coder to encode the d (u) stream, i.e. {∆d (u) (x, y)} stream. The bitrate for encoding the d (u) map is thus computed contour by contour

  (a) Color image of In. (b) d (u) map. (c) Encoding of contour Cn(p).

Fig. 7 .Fig. 8 .

 78 Fig. 7. Encoding of graph edges. (a) Color image of In; (b) Edges of graph described by d (u) map, in which pixels with edges are shown in non-white color (different color denotes different d (u) value); (c) d (u) map is encoded contour by contour, for instance the locations of contour Cn(p) are encoded by a bi-level image (for first pixel) and direction stream (for other pixels), d (u) values on contour Cn(p) are encoded by d (u) stream.

Fig. 9 .

 9 c: the first frames of each video captured by camera 27∼30 are selected (totally 4 views).

  (a) PSNR-rate performance with the true original multiview images as reference. From left to right, Tsukuba dataset, Ballet dataset and Akko&kayo dataset. (b) PSNR-rate performance with the rendered images as reference. The rendered images are obtained by DIBR with I 1 . From left to right, Tsukuba dataset, Ballet dataset and Akko&kayo dataset.

Fig. 10 .

 10 Fig. 10. PSNR-rate performance of multiview representation by different methods on Tsukuba dataset (left), Ballet dataset (middle) and Akko&kayo dataset (right). (a) The PSNR values are computed with the true original multiview images as reference. (b) The rendered images obtained by DIBR with I 1 are the reference.

Fig. 9 .

 9 Fig. 9. Data sets. From top to bottom: color image of reference view I 1 , depth of I 1 and color image of predicted view I 3 .

  (a) Tsukuba dataset. Bitrate around 0.03 bpp. (b) Ballet dataset. Bitrate around 0.1 bpp. (c) Akko&Kayo dataset. Bitrate around 0.08 bpp.

Fig. 11 .

 11 Fig. 11. Visual results. From left to right: Original I 3 , rendered view of I 3 by GBR with AEC-based coding, rendered view of I 3 by GBR with HEVC-based coding and rendered view of I 3 by DIBR with HEVC.

  .a. The predicted views I 2 , • • • , I N are replaced by rendered results I ′ 2 , • • • , I ′ N obtained by DIBR using I 1 and the original depth of I 1 . The graph is constructed using the same parameters as in the experiment in Fig.10.a. The PSNR values of rendered views are computed with I ′ 2 , • • • , I ′ N as reference, which is commonly used in view synthesis literatures

  (a) Depth discontinuity of reference view. (b) d (u) image with frame 1 as predicted view. (c) d (u) image with frame 50 as predicted view.(d) d(u) image with frame 90 as predicted view.

Fig. 13 .

 13 Fig. 13. The proposed GBR simplifies the depth information with respect to the given rendering task. (a) The depth discontinuity of the reference view (frame 100). (b) d (u) image with frame 1 as predicted view. (c) d (u) image with frame 50 as predicted view. (d) d (u) image with frame 90 as predicted view.

  (a) Intermediate view (frame 60). (b) Intermediate view (frame 105). (c) Intermediate view (frame 130).

Fig. 12 .Fig. 14 .

 1214 Fig. 12. Rate-distortion performance of virtual view rendering. The PSNR values are computed with rendered results by DIBR (with original depth) as reference.

  Fig.14.a and b are the color and depth of reference view I 1 . The reconstructed depth of I 1 by GBR is shown in Fig.14.d, in which we can find that the depth has been smoothed. Compared with the true original I 3 in Fig.14.f, the rendered view by GBR in Fig.14.h is of better visual quality than the rendered view by DIBR (with original depth) in Fig.14.g.

• d(u) → graph edge: The edges between I 1 and I 2 are recovered directly from the unidimensional disparity d(u) values; For view I n (2 < n ≤ N ), the edges are estimated using Eq.(1) from the ones between I 1 and I 2 . The edges for disoccluded pixels in I 2 , • • • , I n-1 can be obtained by the same way.

ACKNOWLEDGEMENT

This work has been funded by the regional council of the Brittany Region.