A) Elastic curves

Srivastava et al. [Reference Srivastava, Klassen, Joshi and Jermyn19] introduced a framework to model a continuous evolution of elastic deformations between two reference curves. The referred technique interpolates between shapes and makes the intermediary curves retain the global shape structure and the important local features such as corners and bends.

In order to achieve this behavior, a variable speed parameterization is used, specifically square-root velocity (SRV), so that it is possible to bend one shape into another as well as stretch or compress a certain part of it. Let us introduce some notation. We call p the curve defining the shape, and t ∈ [0, 1] the curve parameter, leading to:

(1) $$p\colon \lsqb 0\comma \; 1\rsqb \rightarrow \lpar x\comma \; y\rpar \in \open{R}^2\comma \;$$

where (x, y) are the coordinates of each point in the contour. Then, p is represented in the SRV space by q:

(2) $$q\colon \lsqb 0\comma \; 1\rsqb \rightarrow \lpar x\comma \; y\rpar \in \open{R}^2\comma \;$$

(3) $$q\lpar t\rpar = \displaystyle{{\dot p} \over \sqrt{\Vert \dot{p}\Vert }}\comma \;$$

where ‖·‖ is the Euclidean norm in ℝ² and $\dot{p} = \displaystyle{dp \over dt}$ . This transformation is reversible (up to a translation): the curve p can reversely be obtained from q by:

(4) $$p\lpar t\rpar = \vint_0^t q\lpar s\rpar \Vert q\lpar s\rpar \Vert ds.$$

Introducing the SRV representation is very interesting because it can be shown that the simple ${\cal L}^{2}$ metric in this space corresponds to an “elastic” metric for the original curve space [Reference Mio, Srivastava and Joshi20], i.e. a metric that measures the amount of “stretching” and “bending” between two curves, independently from a translation, scale, rotation, and parametrization. Moreover, using the SRV it is also relatively easy to compute the geodesic between the two curves: according to the interpretation of the elastic metric, this geodesic consists in a continuous set of deformations that transforms one curve into another with a minimum amount of stretching and blending, and independently from their absolute position, scale, rotation, and parametrization [Reference Srivastava, Klassen, Joshi and Jermyn19]. Classical applications of elastic deformations of curves are related to shape matching and shape recognition. An example of the geodesic connecting two curves is shown in Fig. 1. We show in black two contours extracted (with the Canny edge detector) from the depth of the video sequence “ballet”. These depths correspond to the views 1 and 8, at time instant 2. In red we show the extracted contours of intermediary views, whereas in dashed blue we show a sampling of the elastic geodesic computed between the two extreme curves: it is evident that the elastic deformations along the geodesic reproduce very well the deformations related to a change of viewpoint. Similar results where obtained in the temporal domain: elastic deformations are able to represent the temporal deformation of an object contours, given the initial and final shapes.

Fig. 1. Geodesic path of elastic deformations $\tilde b_s$ from the curve i ₀ to i ₁ (in dashed blue lines). b ₃ is one of the contours b _t extracted from the intermediate frames between the two reference ones, a good matching EC $\tilde b_{0.2}$ along the path is highlighted.

These observations lead us to conceive a lossless coding technique for object contours: supposing that the encoder and the decoder share a representation of the initial and final shapes, they can reproduce the exactly same geodesic path between them. Then, the decoder will conveniently decide which point of the geodesic (one of the blue curves in Fig. 1) shall be used as context information to encode an intermediary contour (one of the red curve in the same figure). The encoder will only have to send a value s* ∈ [0, 1] to identify this curve. If this curve is actually similar to the one to be encoded, it is possible to exploit this information to improve the lossless coding of the latter. However, how to do this is not obvious, and the solution to this problem is one of the main contributions of this paper.

B) Lossless contour coding

Various techniques have been developed to represent and code the boundaries of objects, like polygon approximation [Reference O'Connell21] or chain coding [Reference Katsaggelos, Kondi, Meier, Ostermann and Schuster14]. The latter is the most common method to losslessly encode boundary pixels. A chain code follows the contour of an object and encodes the direction of the next boundary pixel with respect to the current one. Since an object tends to have a quite regular contour it is usually more convenient to code the change of direction with respect to the previous one, thus leading to differential chain codes. An example of differential chain coding of the 8-connected contour of an object is given in Fig. 2. The sequence of symbols produced by a chain code is fed into an entropic encoder, such as a variable length encoder or an arithmetic encoder, possibly using contexts to improve its performance [Reference Cagnazzo, Antonini and Barlaud22].

Fig. 2. Differential chain code: the arrows represent the symbols of the differential chain code if the previous symbol is “Up”. We can code the contour of the object, from the starting point, as: “Up-Left”, 2, − 1, 0, 3, − 1, − 1, 3, − 1, 2, 0, 1, 0.

Recently Daribo et al. [Reference Daribo, Cheung and Florencio17] introduced a new technique aimed at the lossless coding of edges that resulted to be the best among the others. However, it is conceived in a block-based coding environment, we retain it as a base to develop our contour-based coding technique. Their main idea is that contours of a physical object possess geometrical structures that can be exploited to predict the direction of the next symbol, given a window of consecutive previous samples. A chain code is used to represent a contour, and each symbol is encoded with an arithmetic encoder that uses a probability distribution adaptively computed using the previous symbols. The probability distribution is centered around the estimated most probable direction, which in turn is obtained using linear regression (LR) on a suitable window of previous samples: the underlying assumption is that contours exhibit linear trends. The prediction of directions and the assignment of the probability values can be reproduced at the decoder, provided that some parameter is transmitted as side information.

This method has much better performance than other popular techniques [Reference Daribo, Cheung and Florencio17], but further improvements are possible. On the one hand, the LR can be replaced with a more effective estimator for the direction of the next symbol. On the other hand, the encoding algorithm does not take advantage from temporal correlation of contours and the prediction of the most probable direction cannot cope with sudden changes of direction.

Our proposed method uses temporal correlation of contours by producing an elastic estimation of the current curve; this curve is subsequently employed for improving the statistical model of the current symbol of the chain code, resulting in a remarkable improvement of the coding rate. The two reference curves used to produce the elastic deformation are encoded using our improved version of the technique described by Daribo et al. [Reference Daribo, Cheung and Florencio17].

A) Correspondence function

In this subsection, we consider the encoding of a single curve b t using the elastic representation $\tilde{b}_s^{\ast}$ , with s* suitably selected by the encoder. For the encoding of i ₀ and i ₁ we do not use the elastic deformation.

The curves are sampled respectively on N _b and $N_{\tilde b}$ points. To simplify the notation, we will drop the subscript t and s* where this does not give rise to ambiguities.

To use the suitable portion of the synthetic curve $\tilde{b}$ as side information to code the current point on b, it is essential to have a function that associates each point of b to the corresponding point of $\tilde{b}$ . This function is generated at the encoder and has to be transmitted to the decoder.

In order to establish an association between the two curves, we use dynamic time warping (DTW) [Reference Müller23]. First, it is needed to establish a feature space ${\cal F}$ for the curves: a distance in this space will then be used to create the DTW function. Since we want to link the parts of the curve that have the same characteristics in terms of lobes, spikes and such, we used the direction of the tangent vector as featureFootnote ¹ . Let us use a complex representation that associates to every point (x, y) the complex number p = x + ȷ y, and let us refer to the sequence of tangent vectors of the curve c = (x _c , y _c ) as φ _c :

(5) $$\forall n \in \lcub 1\comma \; \ldots\comma \; N_c\rcub \comma \; \varphi_{c}\lsqb n\rsqb = \arg \lpar p_{c}\lsqb n\rsqb - p_{c}\lsqb n - 1\rsqb \rpar \in {\cal F}\comma \;$$

where ${\cal F} = \lsqb -\pi\comma \; \pi\lsqb $ . Computing equation (5) for b and $\tilde{b}$ we obtain the sequences of features φ _b and $\varphi_{\tilde{b}}$ defined on N _b and $N_{\tilde b}$ points, respectively.

A typical behavior of two feature sequences is shown in Fig. 3; while the two sequences have similar shapes, they are not aligned. To perform the alignment we need a local distance measure (or local cost measure), defined as $d \colon {\cal F} \times {\cal F} \rightarrow \open{R}^+$ . The local distance measure d(φ _b [n], $\varphi_{\tilde b}\lsqb m\rsqb $ ) should be small when the two features are similar, large otherwise. Since in our case ${\cal F} \subset \open{R}$ , we can use as distance the square of the direction difference: $\lpar \vert \varphi_{b} - \varphi_{\tilde b}\vert \, \hbox{mod} \, \pi\rpar ^{2}$ . By evaluating the local cost measure for every couple of elements in the sequences, we obtain the cost matrix $C \in \open{R}^{N \times M}$ , where the generic element is defined as follows:

Fig. 3. Example of association of two sequences by DTW.

$$\eqalign{C\lpar n\comma \; m\rpar & = d\lpar \varphi_{b}\lsqb n\rsqb \comma \; \varphi_{\tilde b}\lsqb m\rsqb \rpar \cr &= \lpar \vert \varphi_{b}\lsqb n\rsqb - \varphi_{\tilde b}\lsqb m\rsqb \vert \, \hbox{mod} \, \pi \rpar ^2.}$$

We have to find now the sequence ψ, defined as a sequence of couples:

$$\psi\lsqb \ell\rsqb = \lpar \nu^\ast_\ell\comma \; \mu^\ast_\ell\rpar \in \lcub 1\comma \; \ldots\comma \; N\rcub \times \lcub 1\comma \; \ldots\comma \; M\rcub \comma \;$$

such that:

$$\lpar \nu^\ast\comma \; \mu^\ast\rpar = \arg \nolimits {\min_{\lpar \nu\comma \mu\rpar }} \sum_{l=1}^{L} C\lpar \nu\lsqb \ell\rsqb \comma \; \mu\lsqb \ell\rsqb \rpar $$

under the conditions:

• • boundary condition, ψ[1] = (1, 1) and ψ[L] = (N, M);

• • monotonicity of ν*[ℓ] and μ*[ℓ];

• • step size, ψ[ℓ] − ψ[ℓ − 1] ∈ {(0, 1),(1, 0),(1, 1)}.

In practice, ψ is a sequence of indices (ν*[ℓ], μ*[ℓ]) of the curves φ _b and $\varphi_{\tilde b}$ , such that φ _b [ν*[ℓ]] and $\varphi_{\tilde b}\lsqb \mu^{\ast}\lsqb \ell\rsqb \rsqb $ are best matched under the aforementioned constraints. The association by DTW of the two sequences is shown in dotted black lines in Fig. 3.

In our application, the correspondence function obtained with DTW on the direction of the tangent vector is very close to a straight line and it can be approximated with a first-order polynomial. The approximation has two main effects: first it reduces the number of bits needed to code the function; moreover it prevents sudden variations on the correspondence function that are rather related to outliers than actual values. However, one may wonder whether it is worth computing the exact DTW only for approximating at a first order: maybe a simple rescaling of the “temporal” axis from N points to M points could be as effective as the approximated DTW, without needing to compute the correspondence function. We have dealt with this issue with a simple heuristic approach: we compared the coding rate of our algorithm in two cases: in the first, we use the first-order approximation of the DTW function; in the second we use a rescaling of N/M. We observed that using the DTW gives an average rate reduction of 5.33%. For this reason, we kept the DWT in our system.

In Fig. 4, there is an example of DTW and its linear approximation. The resulting correspondence between the points of the two curves is shown in Fig. 5. We see that all the main features of the curves are located and put in correspondence, so that for each point of the actual curve b there is an associated point on the EC $\tilde{b}$ , whose neighborhood is the side information we want to use to enhance the coding of b.

Fig. 4. Ballet: correspondence function. In blue the association of the two curves using the DTW of the direction of the tangent vector, in dashed red the approximation with a first-order polynomial, whereas n and m are the indices of samples on the curves b and $\tilde{b}$ , respectively.

Fig. 5. Ballet: correspondences between the EC $\tilde{b}$ (dashed blue) and the curve to code b (red).

B) Context

The correspondence function allows us to associate the current point to a portion of the EC, centered in the corresponding point. This information is used as side information to have more accurate probability values for the next symbol. We called this information the context, and for each point of the curve b, it is composed by:

• • v ₀, a vector of N ₀ points of the curve b transmitted so far (in red in Fig. 6);

• • v _{1 p} : the “past” on the EC (in dashed blue in Fig. 6), a vector of N _p points of $\tilde{b}$ corresponding to v ₀; more precisely, v _{1 p} is constituted of the points between those corresponding to the terminal points of v ₀;

• • v _{1 f} : the “future” on the EC, a vector of N _f points of the EC $\tilde{b}$ following the current correspondent point on $\tilde{b}$ (in dark blue in Fig. 6).

Fig. 6. Extracts from the curves b (red) and $\tilde{b}$ (dashed blue). The correspondences between the two curves are indicated with thin dotted black lines. The dashed lines represent the extracted direction for the vectors of points v ₀, v _{1 p} , and v _{1 f} .

Of course v _{1 p} and v _{1 f} are only available for B-contours, for I-contours only v ₀ is available. We use the context to obtain the most probable direction for the next symbol, then we use this result to define a distribution using the von Mises statistical model [Reference Mardia and Jupp24].

1. Direction extraction

For all the set of points of the different curves, we have to estimate the direction of the next symbol. In the case of the I-contours, only the set of points p ₀ are used, whereas in the case of B-contours all the three sets of points v ₀, v _{1 p} , and v _{1 f} are used.

Several approaches can be used to extract a direction from a set of ordered points. E.g. in [Reference Daribo, Cheung and Florencio17] an LR on v ₀ is used. We found that a simple average direction (AD) is even more effective. Using the same complex representation as in IIIA, the estimated direction α can be obtained using the following formula:

(6) $$\alpha \lpar {\bf v} \rpar = \arg\left(\displaystyle{1 \over N-1} \sum_{n=2}^{N}\lpar {\bf v}\lsqb n\rsqb - {\bf v}\lsqb n - 1\rsqb \rpar \right)\in \lsqb -\pi\comma \; \pi\rsqb \comma \;$$

where v is the complex representation of a generic vector of N points, and is defined as v = [x ₁ + ȷ y ₁, x ₂ + ȷ y ₂, …, x _N  + ȷ y _N ]; arg is the argument of a complex number.

2. Most probable direction

Applying α on the complex representation of v ₀, we obtain α₀, the angle of the AD based solely on the previously transmitted samples. Likewise, α_{1 p} and α_{1 f} are the ADs based on the vectors v _{1 p} and v _{1 f} of the curve $\tilde{b}$ . We develop a method to estimate θ, the most likely direction of next symbol of b: we use α_{1 f} to adjust the direction α₀. In this way, we manage to seize the sudden changes and go along the long trends.

A simple and intuitive formula to take into account the context for the prediction of the most probable direction is:

(7) $$\theta = \lpar 1 - q\rpar \alpha_0 + q \alpha_{1 f}\comma \;$$

with q ∈ [0, 1]. This way we can weight the directions of the past of the curve b and the future of the curve $\tilde{b}$ . To decide the weight q, we observe that the side information of the EC is not essential when the curves are regular, while it becomes fundamental next to the occurrence of a sudden change. So q should be small if for the current point the directions extracted from the two curves are similar (so that θ is close to α₀), and close to 1 if they are not (so that θ close to α_{1 f} ):

(8) $$q = \displaystyle{{\max \lcub \vert \alpha_0 - \alpha_{1 p}\vert \comma \; \vert \alpha_0 - \alpha_{1 f}\vert \rcub }\over{\pi}}.$$

The value of q is related to the modulus of the difference of directions, and it is large if α₀ is very different from α_{1 p} or α_{1 f} because a dissimilarity in the neighborhood of the current point suggests a change which is not predicted solely from α₀.

3. Adaptive statistical model

We retain the statistical model described in [Reference Daribo, Cheung and Florencio17] to assign values to the symbols for the next edge. It is based on the von Mises distribution and the distribution parameters are set according to the information extracted from the curves b and $\tilde{b}$ . The von Mises distribution is the Gaussian distribution for angular measurements and it is defined as [Reference Mardia and Jupp24]:

(9) $$p\lpar \beta\vert \mu\comma \; \kappa\rpar = \displaystyle{{e^{\kappa \cos\lpar \beta - \mu\rpar }} \over {2 \pi I_0\lpar \kappa\rpar }}\comma \;$$

where I ₀(·) is the modified Bessel function of order 0, μ is the mean and in this case it coincides with the estimated direction θ, 1/κ is the variance of the distribution. As in [Reference Daribo, Cheung and Florencio17], we set κ as a function of the predicted direction θ: when θ is aligned with the axis of the pixel connection grid, intuition tells us that it is more convenient to give a higher probability value to the symbol that represents that direction. So κ is set to:

(10) $$\kappa = \rho \cos\lpar 2\hat{\theta}\rpar \comma \;$$

where $\hat{\theta} = \min\lcub \vert \theta - \gamma_{i}\vert \rcub $ , and γ _i are the angles of the pixel connection grid ( $\left\{0\comma \; \displaystyle{\pi\over 8}\comma \; \displaystyle{2\pi\over 8}\comma \; \ldots \right\}$ in the case of an eight-connected grid). The parameter ρ represents a “confidence level” of the prediction: as it grows it makes the distribution more unbalanced, so the more precise is the prediction based on the context, the larger it should be to achieve higher coding gains.

C) Coding

The curve b, represented with a differential chain code, is encoded with an arithmetic coder which for each symbol uses the probability vector assigned by the adaptive statistical model. The encoder needs to transmit to the decoder the parameters involved in the coding process:

• • s*, the selected point on the geodesic path;

• • the correspondence function, approximated by a first-order polynomial, so two parameters;

• • the parameter ρ;

• • N ₀ and N _f .

With this information the decoder can reproduce the behavior of the encoder and it will compute the same probability values for each point of the curve b. We observe that N _p does not need to be sent, since it is deduced by applying the correspondence function to v ₀.

A) Coding of I- and B-contours

To code the I-contours we replaced the LR with the more effective AD in the technique described in [Reference Daribo, Cheung and Florencio17], whereas for the coding of the B-contours we can take advantage of the context provided by the ECs, thus achieving better coding gains. In Table 1, are shown the results for a set of images taken from the test sequences. We notice that just altering the direction extraction method from LR to AD the average coding cost is reduced by 4.88%, while passing from AD to AD with EC context leads to a reduction of 1.82%, for a total reduction of 6.53%. If on the other hand we use the LR with the EC context, then the rate reduction is 2.25%.

Table 1. Coding results (in bits) for the different contributions of the developed tools to the technique proposed in [Reference Daribo, Cheung and Florencio17], applied to object contours. Two different methods to extract the probable direction from a set of points: linear regression (LR), and average direction (AD), without and with elastic curve (EC) context.

B) Side information cost

We will now account for the cost to transmit the four parameters s*, N _p *, N _f *, and ρ*, as well as the correspondence function.

The correspondence function is the result of a linear approximation and experiments show that using 10 bits to code the two parameters of the straight line leads to the same performance as coding them with double precision.

For N _p * and N _f * we decided to use 1 bit for the range of N _p ({5, 6} ), and 2 bits for the range of N _f ({6, 7, 9, 11} ), once again based on experimental results. On the other hand, the optimal ρ has a wider range of values, and we observed that typical values can be represented by the set {6.6 + kΔ}, with Δ = 0.1 and k = 0, …, 31, for a cost of 5 bits.

We observe that the accuracy of the representation of the position on the geodesic s* has a quite large influence on the coding efficiency. Using for example 2 bits to code the possible positions we have four curves to use as side information to code the curve b, using 3 bits leads to eight curves, in general using a fixed length representation with b _s bits permits us to choose among 2 ^{b _s} different curves. The chance of finding a good matching curve to use as a side information increases with b _s , but for every bit added the complexity doubles, and we are increasing the cost of the representation too. If some values are more probable than others it is worth to consider a variable length code to reduce the cost of the representation.

We thus used an experimental approach and compared two different ways to code s*: a fixed length coding, with length from 2 to 10, and an Exponential-Golomb code. In Table 2, we see that, performing the average on different curves and on different sequences, a fixed length coding leads to better performance if the number of bits used for the representation of s* approaches to 6 or more. To compare the proposed method to other techniques we choose the best performing 10 bits fixed length coding.

Table 2. Average coding cost (in bits) for different ways of coding s*: fixed length coding up to 10 bits and Exp-Golomb.

For the I-contours we only have to transmit as side information the parameters N _p * and ρ*, corresponding to an overall cost of 6 bits. On the other hand, the decoding of the B-contours needs the correspondence function as well as the four parameters N _p *, N _f *, ρ*, and s*, corresponding to an overall cost of 28 bits.

C) Greedy algorithm (GA)

Resting on experimental results for each variable we selected a range of typical values. We initialize the GA with a starting point (N _p0, N _f0, ρ₀, s ₀), corresponding to the solution in which every value is the closest to the center of the coded range, and then the GA optimizes the variables in the order N _p , N _f , ρ, s. Keeping fixed N _f0, ρ₀, and s ₀ the GA runs the proposed technique to select the N _p that minimizes the bit rate. Once N _p * has been found the algorithm starts again to optimize N _f from the point (N _p *, N _f0, ρ₀, s ₀). Then again for ρ and s, until it reaches the solution (N _p *, N _f *, ρ*, s*).

The search order for the parameters is set according to our observations of the optimum parameter distributions after the full search for many sequences: N _p * has a very peaked distribution, so the selected value after the first step of the GA should actually be the best one. N _f *, on the contrary, has an almost uniform distribution, thus making difficult to locate the best value; it is however required to select it before ρ*, because the best value of ρ is influenced by the selected values of N _p and N _f . Still based on our observations, the last parameter to select is s.

As we can see in Table 3, the average loss with respect to the full search is 0.82%, but the number of calculations the encoder has to do is approximately reduced by a factor of 250.

Table 3. Average coding cost (in bits) for the full search and the greedy algorithm (GA).

Regarding the overall time needed for the coding of a curve, we can distinguish fixed and variable time contributions. The elastic estimation is fixed but we can decide how many frames to leave in between the two reference ones. On the other hand, the execution time for the choice of the parameters can vary greatly: a full search is very costly, and even if the GA speeds up the whole process, one can also decide to keep the same parameters (or a subset of the parameters) for a certain number of frames.

D) Comparisons

We compare our technique to various methods to code the differential chain code of the contours: Adaptive Arithmetic Coder (AAC), Context Based Arithmetic Coder (CBAC), and the technique proposed in [Reference Daribo, Cheung and Florencio17].

In the compression of B-contours, we achieve gains up to 10% compared to the method of [Reference Daribo, Cheung and Florencio17], but to make a fair comparison we have to consider for our technique both I-contours and B-contours of the GOP structure. To study the influence of the GOP structure on the coding performance we used the following:

• • IBIBIB … is very effective for the B-contours, since the two reference frames are very close and the prediction is very accurate, but the I-contours have a non negligible cost on the final outcome. Using this GOP structure produced in our experiments an average bit rate of 1000,19 bits per contour;

• • IBBIBB … and IBBBIBBB … are flat structures with fairly distant I-contours, they produced an average bit rate of 1004.03 and 1010.28 bits per contour, respectively;

• • I₁B₁B₂B₃I₂ … is a hierarchical structure with 5 frames in the GOP, in which B₂ is predicted using I₁ and I₂, B₁ using I₁ and B₂, and so on. It produced an average bit rate of 997,57 bits per contour.

The hierarchical structure proved to be the most effective GOP structure: the cost of the I-contours is low and the elastic prediction for B₂ is just slightly less accurate than the ones for B₁ and B₃. This result is expected, given the previous study on depth map compression with traditional hybrid techniques that shows the importance of the prediction order [Reference Maugey and Pesquet-Popescu29].

In Table 4, the average results for the test sequences are shown, and in every case our technique performs better than the others. The overall average gain with respect to the second best coding technique in the group, the one proposed in [Reference Daribo, Cheung and Florencio17], is 6.53%. If we consider instead the gain of the proposed technique with respect to JBIG2, which is not optimized for this kind of data but has been chosen to code the boundary information in [Reference Gautier, Le Meur and Guillemot8], it is 65.09%. Over other standard techniques, such as AAC and CBAC (with one symbol context, the best choice in our tests) the average gains are of 23.93 and 18.06%, respectively.

Table 4. Average coding cost (in bits) for various sequences in the view domain (ballet) and in the time domain (mobile, lovebird, beergarden, stefan). The tested methods are: JBIG2, Adaptive Arithmetic Coder (AAC), Context Based Arithmetic Coder (CBAC) with 1 symbol context, the one proposed in [Reference Daribo, Cheung and Florencio17], and the proposed technique (all the side information cost accounted). In the last column are reported the gains of the proposed technique over the other best performing one in the group.

E) Object-based depth maps coding technique

We underline here that the goal of this paper is not to propose a complete system for MVD coding, but only to show the potential of the lossless contour coding based on elastic deformation. In this respect, we show that a relatively simple codec based on this tool may be competitive with (or even better than) the state of the art and this may be considered a validation of the proposed approach.

Coming to the implementation, we observe that it is very difficult to integrate our object-based technique into a 3DVC coder. We resort to an existing object-based technique since it can immediately benefit from an improved contour coding method, even though it is not the best option from an rate-distortion (RD) perspective. Despite the simplicity of the approach, as we will show, we have satisfying results, due to the nature of the data we want to compress. In summary, the new object-based compression technique is composed of:

• • the proposed technique for the contours of the object with a hierarchical GOP structure I₁B₁B₂B₃I₂, as described in Section IVD. This part provides a lossless coding with inter-frame prediction;

• • for the inner part of the objects we use the Shape Adaptive (SA) Wavelet Transform, followed by SA Set Partitioning In Hierarchical Trees (SPIHT), followed by an arithmetic coder [Reference Cagnazzo, Poggi, Verdoliva and Zinicola30]. We remark that for the inner part of the objects we thus have an entirely “Intra” technique.

We have chosen this technique because it is reasonable and simple, and it complements perfectly with our lossless coding technique.

To make a meaningful comparison we used HEVC Intra to compress the depth maps. We believe that the comparison is fair because in the case of HEVC Intra the arithmetic coder for the lossless coding part take advantage of the context updating, and there is no temporal prediction. Likewise, in our technique, the lossless coding part exploits the temporal redundancy, while the object coding is totally “Intra”. Moreover, it would not be fair to make a comparison with HEVC Inter because we have no temporal prediction for the objects, neither would be easy to develop an object-based coder with temporal prediction.

Once defined the compression technique, we use the decoded depths to synthesize new views and make a comparison with the images generated by the uncompressed depth maps. Given any two adjacent views of the multiview sequence, we generated three equally spaced synthetic intermediate views. To test our depth maps compression technique we used the multiview sequences ballet, beergarden, lovebird and mobile, synthesizing 6, 15, 30, and 54 frames, respectively. In order to assess the quality of the virtual views, we compared them to synthesized images obtained by applying the same DIBR algorithm to the uncompressed depths and views, and thus we obtained the RD points related to our techniques and to HEVC Intra.

Finally, we computed the Bjontegaard metrics [Reference Bjontegaard31] on these RD points: we observed that our technique outperforms the reference for ballet, beergarden and mobile, achieving respectively +2.6 dB, +0.16 dB and +0.88 dB, while the PSNR was practically identical for lovebird. These results, however, pertinent to quite specific test conditions (PSNR of synthesized images, limited range), show that our technique can perform at least as well as HEVC Intra, or even better depending on the sequence: these results imply that the proposed approach is worth considering. This is even more relevant in sight of the fact that in general, object-based coding techniques achieve not very good results in image compression. It has been shown that the cost of lossless contour coding is one of the elements that undermine these techniques the most [Reference Cagnazzo, Parrilli, Poggi and Verdoliva10].