<figure><img src="image_1.png" /></figure>

HAL
open science

# Disparities selection controlled by the compensated image quality for a given bitrate

Imen Kadri, Gabriel Dauphin, Anissa Mokraoui, Zied Lachiri

► To cite this version:

Imen Kadri, Gabriel Dauphin, Anissa Mokraoui, Zied Lachiri. Disparities selection controlled by the compensated image quality for a given bitrate. Signal, Image and Video Processing, 2020, 14 (6), pp.1143 - 1151. 10.1007/s11760-020-01643-1 . hal-03916041

HAL Id: hal-03916041

https://hal.science/hal-03916041

Submitted on 8 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Disparities selection controlled by the compensated image quality for a given bitrate

3 Imen Kadri<sup>a,b</sup>, Gabriel Dauphin<sup>a</sup>, Anissa Mokraoui<sup>a</sup>, Zied Lachiri<sup>b</sup>

4 <sup>a</sup>L2TI, Institut Galilée, Université Paris 13, Villetaneuse, France,

5 <sup>b</sup>LSITI, Ecole Nationale d'Ingénieur de Tunis, Université de Tunis El Manar, Tunis, Tunisie,

**Abstract.** Stereoscopic images consist of two views rendering a depth sense. The small objects displacements across the two views are interpreted as a relative indication of depth. From a compression viewpoint, these displacements are exploited as specific inter-view redundancies. The classical and still compression scheme in use is called Disparity Compensated Compression scheme. A block-based disparity map modeling these displacements is losslessly compressed. Then the difference, between the original view and its disparity predicted view, is compressed and used by the decoder to compute the compensated view improving therefore the disparity predicted view. However, a proof-of-concept work has already shown that selecting disparities according to the compensated view, instead of the predicted view, yields increased rate-distortion performance. This paper derives from the JPEG-coder, a disparity-dependent analytic expression of the distortion induced by the compensated view. This analytic expression is embedded into an algorithm, called Fast Disparity Compensated Block Matching algorithm (FDCBM), with a reasonable numerical complexity approaching the performance obtained with the proof-of-concept work. Tested on stereoscopic images, the proposed algorithm provides, at same bitrate, an average performance increase of 0:54dB as compared to the classical stereoscopic image coding scheme, when performance is measured by the Peak Signal to Noise Ratio.

19 **Keywords:** Stereoscopic Image Compression, Disparity-Compensation, Block Matching algorithm, JPEG-Distortion.
20

## 1 Introduction

21 Immersive multimedia combines near-to-reality outputs that users can experience through the sense of sight, hearing, touch and even smell. This immersive perception may also be rendered through interactive control of the viewpoint. Applications concern medical intervention, education and live production industry.¹ A hologram is an image that appears to be three dimensional as it changes with the relative position of the observer, being very precise, it can be used to record the complete 3D information of a scene.² A stereoscopic image is composed of two views which are perceived as two viewpoints of a single 3D-scene, thanks to a technical device (anaglyph, LC shutter or polarized 3D system), applications concern the entertainment industry (3D cinema), video games, medical field (stereoscopic displays) and cartography (aerial stereo-photography).³ An integral
31 image is a generalization of stereoscopy in which a large number of different viewpoints is used
32 instead of two. It yields depth perception without using any technical device on the user's side.⁴

33 From an information technology viewpoint, all these displayed contents require a very large
34 amount of data which causes issues with storage, transmission and sometimes real-time displaying.
35 Such data is used in many 3D-research activities⁵ to estimate the depth map, generally assuming
36 that objects look the same when seen from different views, which happens to be not so common.⁶
37 Research in compression aims at reducing that amount of data by exploiting redundancies. In some
38 applications, the depth map is also needed to generate an intermediate virtual view or to adjust the
39 depth perception to improve the quality of experience.

40 This paper focuses on the stereoscopic images compression.⁷⁻⁹ In this context, the depth map
41 is *not* by itself an issue and it is needed only in that it explains the differences between the two
42 views (a close object of a 3D-scene appears on both views at two distant locations). The horizontal
43 distance between the two similar points is called the *disparity*. It is inversely related to the depth.
44 Therefore stereoscopic images can be represented as a 2D image and a depth map with which it is
45 possible to recover the other view using view synthesis. Research in this context includes sparse
46 encoding of the depth map, image warping, inpaiting to fill in disoccluded regions.⁶ The depth
47 map is sometimes encoded as a disparity map as for lifting schemes where the view synthesis
48 is achieved using a set of predict and update filters in a multi-resolution context. Correlations
49 between depth map texture and motion are exploited in Ref. 6. In Ref. 10, the authors used also
50 view synthesis optimization, meaning that the choice of the depth map takes also into account
51 the reconstruction of the other view, while using a different framework, this idea is at the core
52 of our present work. Besides it should be said, that high performance is achieved when different
53 techniques are combined as in Multiview Video Coding (MVC) extension of H264/AVC video
54 coding standard ¹¹ which has been subjectively evaluated in Ref. 12.

As in Refs. 13, 14, this paper proposes to work with the original framework, called the Disparity Compensated Compression scheme (DCC), exploiting the stereoscopic image redundancy. It consists in coding separately a reference view, losslessly encoding an estimated disparity map and then encoding a residual image. The transmitted information enables the decoder to reconstruct the reference view, and using the disparity map to compute a predicted view to which is added the decoded residual image. Note that the DCC scheme shares some similarities with the depth and view synthesis representation in that, depth information is here modeled as a block-based disparity map and the texture information is featured by the lossy-encoded residual image. The DCC scheme is very similar to motion/disparity compensation. This scheme is implemented in the HEVC and the MVC extension of the H264/AVC video coding standards.

Research within this framework has achieved increased performance when estimating the disparity map, by taking into account its own bit-cost in Refs. 15, 16 and its limited predicting capacity,¹⁷ by using blocks of arbitrary shapes in Ref. 18, and by addressing also the illumination compensation in Ref. 19. Investigating the statistical properties of the residual, reference²⁰ uses a DCT-based coder for non-occluded 8×8-blocks and a 3-level Haar-based coder for occluded 8×8-blocks to encode the residual instead of the JPEG-coder.²¹ Reducing the numerical complexity is also a significant research issue. Examples include selecting optimal hyper-parameter values thanks to allocation modeling as opposed to an exhaustive search in Ref. 22 reducing the search area in Ref. 23 and using embedded coding scheme that can be truncated at any point to obtain the best reconstruction for a given bitrate.²⁰

At the core of our work is the idea, that the estimation of the disparity should take into account, the ability of the residual coder to refine the predicted view, instead of assuming that the best
77 predicted view yields the best compensated view. In the context of the JPEG-residual encoder, a
78 proof of concept using a very greedy algorithm has already shown increased performance in .<sup>24</sup> Our
79 contribution is the design of an algorithm with a reasonable numerical complexity, able to select
80 the disparity according to the compensated predicted view in order to improve the rate-distorsion
81 performance of the compressed stereoscopic image.

82 This paper is organized as follows. Section 2 summarizes the basic concepts of the classi-
83 cal DCC scheme and introduces some notations. Section 3 shows how finding the best perform-
84 ing disparity map can be regarded as solving an optimization problem. The classical approach,
85 called the Block-Matching algorithm (BM), is derived as a suboptimal solution. Section 4 recalls
86 the greedy algorithm solving the optimization problem, it is called the Disparity-Compensated
87 Block-Matching (DCBM) algorithm. Section 5 describes an extension of this algorithm called
88 Fast Disparity-Compensated Block-Matching (FDCBM) algorithm. In Sec. 6, experiments show
89 significant increased performance on some stereoscopic images. Section 7 concludes the paper.

90 **2 Basic concepts and notations**

91 This paper deals with compressing rectified stereoscopic images using the classical DCC scheme.
92 Notations are first given and used in Sec. 3 to set the optimization problem, to which the well-
93 known Block Matching (BM) algorithm is a suboptimal solution.

94 Notations, used in the following sections, are summarized in Fig. 1. This figure presents the
95 DCC scheme where the dashed line separates the encoder (above) from the decoder (below).

96 $I_l$ (upper left corner in Fig. 1) denotes the left view that is here chosen as the reference view. It
97 feeds a lossy encoder
denoted $C_{ql}$ (upper left corner in Fig. 1) where $q_l \in Q_l$ is its quality factor with $Q_l$ is a set containing all allowed values. The bit stream output is transmitted to the decoder (left downward arrow connecting the dashed line). This bit stream is decoded by $D_l$ yielding a reconstructed left view denoted $\hat{I}_l$ (lower left corner in Fig. 1) as follows:

$$ \hat{I}_l = D_l(C_{ql}(\hat{I}_l)). \qquad (1) $$

Note that the framework chosen uses a close loop as this bit stream yields also $\hat{I}_l$ in the encoder through $D_l$ (center upper part in Fig. 1). $\hat{I}_l$ feeds the remaining compressing part. Such a choice reduces the distortion as $\hat{I}_l$ is not available to the decompressing part but it also increases the numerical complexity as the remaining compressing part depends on the choice of $q_l$.

$\hat{I}_r$ (center of the upper part in Fig. 1) represents the original right view. With $\hat{I}_l$, it is used by the Disparity Estimator (DE) to yield a disparity map denoted $d$ using the well-known BM algorithm. $d$ is then used by the Image Predictor (IP) to transform $\hat{I}_l$ into the predicted view, denoted $\hat{I}_p$.

More specifically, $\hat{I}_l$ and $\hat{I}_r$ are decomposed into $K$ non-overlapping blocks of same size (both views may have to be slightly enlarged to cover the last block column and the last block line). The upper left corner of the $k$-block is indicated by coordinates $(i_k, j_k)$. The pixels contained in the $k$-block are referred to by $(i_k + \Delta i, j_k + \Delta j)$ where $(\Delta i, \Delta j)$ spans $\mathcal{B}$, a set listing all internal-block displacements (including $(0, 0)$). $d$ is an array of $K$ disparity values denoted as $d_1, \dots, d_K$. It describes the $K$ right horizontal-shifts by which, in the IP-block, each $\hat{I}_l$-block is transformed into
an $\mathbf{I}_p$-block:

$$ \mathbf{I}_p \left( \begin{bmatrix} i_k + \Delta i, \\ j_k + \Delta j \end{bmatrix} \right) = \hat{\mathbf{I}}_l \left( \begin{bmatrix} i_k + \Delta i, \\ j_k + \Delta j + d_k \end{bmatrix} \right), \quad (2) $$

where $k$ ranges from 1 to $K$ and $(\Delta i, \Delta j)$ spans $\mathcal{B}$. This IP-block is shown on the upper right part in Fig. 1. To simplify notations, we do not indicate here the $d$-dependency of $\mathbf{I}_p$.

BM algorithm, in the DE-block, consists in selecting for each $k$-block, the disparity value $d_k$ for which the $k$-block $\mathbf{I}_p$-values resemble most the $k$-block $\mathbf{I}_r$-values in the sense that the mean squared error is minimized as follows:

$$ d_k(q_l) = \arg \min_{d \in \mathcal{S}} \sum_{(\Delta i, \Delta j) \in \mathcal{B}} \left( \hat{\mathbf{I}}_l \begin{bmatrix} i_k + \Delta i \\ j_k + \Delta j + d \end{bmatrix} - \mathbf{I}_r \begin{bmatrix} i_k + \Delta i \\ j_k + \Delta j \end{bmatrix} \right)^2, \quad (3) $$

where $\mathcal{S}$ contains all allowed disparity values. As $\hat{\mathbf{I}}_l$ is $q_l$-dependent, the disparity value found, $d_k$ is also $q_l$-dependent.

$C$ (center upper part in Fig. 1) is a lossless encoding operation of the disparity map $\mathbf{d}$. The resulting bit stream is transmitted to the decoder (center downward arrow connecting the dashed line) which recovers the exact disparity map $\mathbf{d}$, through $D$, being the inverse operation of $C$ as follows:

$$ \mathbf{d} = D(C(\mathbf{d})). \quad (4) $$

The recovered disparity map is used with $\hat{\mathbf{I}}_l$ by the second IP-block to yield according to Eq. (2),
I_p, this time in the decoder. This second IP-block is at the bottom in Fig. 1.

R (upper right corner in Fig. 1) represents the residual image, that is the difference between
the original right view and its prediction:

$$
\mathbf{R} = \mathbf{I}_r - \mathbf{I}_p. \tag{5}
$$

C<sub>qr</sub> (upper right corner in Fig. 1) is a lossy encoding operation where q<sub>r</sub> &isin; Q<sub>r</sub> is its quality
factor and Q<sub>r</sub> is the set of all allowed values. C<sub>qr</sub> compresses R into a bit stream transmitted to
the decoder (right downward arrow connecting the dashed line). D<sub>r</sub>, being the inverse operation
of C<sub>qr</sub>, is used in the decoder to get an approximation of R denoted R&macr;. By reversing Eq.(5), the
decoder gets an approximation of I<sub>r</sub> denoted as I&macr;<sub>r</sub> and given by:

$$
\hat{\mathbf{I}}_r = \mathbf{I}_p + D_r(C_{qr}(\mathbf{R})). \tag{6}
$$

In general, $\hat{\mathbf{I}}_r$ is closer to $\mathbf{I}_r$ than $\mathbf{I}_p$ and this improvement of $\mathbf{I}_p$ is being referred to as *compensation*.

The bitrate, denoted $b$, is deduced from the bit streams $C_{ql}(\mathbf{I}_l)$, $C(\mathbf{d})$ and $C_{qr}(\mathbf{R})$:

$$
b(\mathbf{I}_l, \mathbf{d}, \mathbf{I}_r, q_l, q_r) = \frac{|C_{ql}(\mathbf{I}_l)| + |C(\mathbf{d})| + |C_{qr}(\mathbf{R})|}{|\mathbf{I}_l| + |\mathbf{I}_r|}, \quad (7)
$$

where |.| is the set cardinal number, here it helps counting, above, the number of bits, and below,
the number of pixels.
<figure><img src="image_3.png" /><figcaption>Fig 1 DCC scheme where the encoder (above) is separated from the decoder (below) by a dashed line.</figcaption></figure>

3 Optimization problem statement

The aim of a coding/decoding scheme is a trade-off between getting the highest quality (i.e. visual
rendering) while using the least amount of bits accounted for by Eq.(7). In this paper, this trade-off
is rephrased into finding the best quality within a constrained bit budget. As the end user observing
the reconstructed stereoscopic image is generally a human being, our focus should be the extent
to which the visual experience is being preserved. Regardless of how that visual experience is
measured, we have chosen to use J, the mean squared error between (Î_l, Î_r) and (I_l, I_r), as the
cost function to be minimized with respect to a bit-budget, b_a.

More specifically, the mean squared error of the *k*-block of an image *I*′ as compared to that of
an image *I* is:

$$
J_k(\mathbf{I}', \mathbf{I}) = \frac{1}{|\mathcal{B}|} \sum_{(\Delta i, \Delta j) \in \mathcal{B}} \left( \mathbf{I}' \begin{bmatrix} i_k + \Delta i \\ j_k + \Delta j \end{bmatrix} - \mathbf{I} \begin{bmatrix} i_k + \Delta i \\ j_k + \Delta j \end{bmatrix} \right)^2 . \quad (8)
$$
Averaging $J_k$ over all blocks yields $J$:

$$J(\mathbf{I}', \mathbf{I}) = \frac{1}{K} \sum_{k=1}^{K} J_k(\mathbf{I}', \mathbf{I}). \qquad (9)$$

The cost-function is then defined as:

$$\mathcal{J}(\hat{\mathbf{I}}_l, \mathbf{I}_l, \hat{\mathbf{I}}_r, \mathbf{I}_r) = \frac{1}{2} J(\hat{\mathbf{I}}_l, \mathbf{I}_l) + \frac{1}{2} J(\hat{\mathbf{I}}_r, \mathbf{I}_r). \qquad (10)$$

This choice of cost function gives way to an optimization problem. $\hat{\mathbf{I}}_r$ is actually $(q_l, q_r, \mathbf{d})$-dependent as stated by Eqs.(1), (2), (5) and (6). $\hat{\mathbf{I}}_l$ is $q_l$-dependent (see Eq.(1)). Such dependencies are indicated here:

$$\left\{
\begin{aligned}
\mathbf{d}(q_l, q_r) &= \underset{\mathbf{d} \in \mathbf{S}^K}{\arg \min} \ J(\hat{\mathbf{I}}_r(q_l, q_r, \mathbf{d}), \mathbf{I}_r) \\
(q_l, q_r) &= \underset{q_l \in \mathbf{Q}_l, q_r \in \mathbf{Q}_r, b \le b_a}{\arg \min} \ \mathcal{J}(\hat{\mathbf{I}}_l(q_l), \mathbf{I}_l, \hat{\mathbf{I}}_r(q_l, q_r, \mathbf{d}(q_l, q_r)), \mathbf{I}_r)
\end{aligned}
\right.
\qquad (11)$$

where $b$, defined in Eq. (7), depends on $\mathbf{I}_l, \mathbf{d}, \mathbf{I}_r, q_l, q_r$. $\mathbf{S}^K$ is the set of all arrays of size $K$ whose components are in $\mathbf{S}$ and $b_a$ is the expected bitrate.

Investigating the link between the BM algorithm and this optimization problem, Eq. (3) can be recast into:

$$d_k(q_l) = \underset{s \in \mathbf{S}}{\arg \min} \ J_k(\mathbf{I}_p, \mathbf{I}_r). \qquad (12)$$
**Algorithm 1 BM algorithm**

**Input:** $\mathbf{I}_l, \mathbf{I}_r, q_l, q_r$

**Output:** $C_{q_l}(\mathbf{I}_l), C(\mathbf{d}), C_{q_r}(\mathbf{R}), b, \mathcal{J}$

Compute $C_{q_l}(\mathbf{I}_l), \hat{\mathbf{I}}_l$ with (1) and $J(\hat{\mathbf{I}}_l, \mathbf{I}_l)$ with (8) and (9)

**for all** $k \in \{1...K\}$ **do**

**for all** $d \in \mathbf{S}$ **do**

Compute the $k$-block of $\mathbf{I}_p$ with (2) and $J_k(\mathbf{I}_p, \mathbf{I}_r)$ with (8)

**end for**

Select $d_k$ with (12) minimizing $J_k(\mathbf{I}_p, \mathbf{I}_r)$

**end for**

Collect $\mathbf{d} = (d_1, ..., d_K)$ and compute $C(\mathbf{d})$

Compute $\mathbf{I}_p$ with (2), and $\mathbf{R}$ and $C_{q_r}(\mathbf{R})$ with (5)

Compute $\hat{\mathbf{I}}_r$ with (6) and $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$ with (8) and (9)

Compute $\mathcal{J}$ with (10) using $J(\hat{\mathbf{I}}_l, \mathbf{I}_l)$ and $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$

Compute $b(\mathbf{I}_l, \mathbf{d}, \mathbf{I}_r, q_l, q_r)$ with (7) using $C_{q_l}(\mathbf{I}_l), C(\mathbf{d}), C_{q_r}(\mathbf{R})$

When considering the whole array of disparities, Eq. (12) becomes:

$$ \mathbf{d}(q_l) = \arg\min_{\mathbf{d} \in \mathbf{S}^K} J(\mathbf{I}_p, \mathbf{I}_r). \qquad (13) $$

Equation (13) is different from Eq. (11) only in that $\mathbf{I}_p$ is considered instead of $\hat{\mathbf{I}}_r$. This difference is actually the decoded-encoded residual as stated by Eq. (5) and (6):

$$ \hat{\mathbf{I}}_r - \mathbf{I}_p = D_r (C_{q_r}(\mathbf{I}_r - \mathbf{I}_p)). \qquad (14) $$

Hence, the BM algorithm can be regarded as a suboptimal solution of Eq. (11), where the effect of the choice of the disparity on the residual, and the residual impact on the distortion, are neglected.

Algorithm 1 summarizes the DCC algorithm using BM strategy (to simplify the presentation, the greedy selection of $q_l$ and $q_r$ is not shown here). Note that from then on, this DCC algorithm is referred to as BM algorithm.
4 Disparity compensated block matching algorithm, a greedy algorithm

This section presents the Disparity Compensated Block Matching (DCBM) algorithm already de-
veloped in Ref. 24. The DCBM algorithm is different from the BM algorithm in that Eq. (11) is
no longer simplified into Eq. (13). The DCBM algorithm is derived from a different suboptimal
solution involving much greater numerical complexity.

The DCBM algorithm is computed in K + 1 steps. In the first step, the disparity map is
computed using the BM algorithm. This initial disparity map has the K following components:

$$
d_k(0, q_l) = \arg \min_{d \in S} J_k(\mathbf{I}_p, \mathbf{I}_r), \quad (15)
$$

where *k* ranges from 1 to *K*. Note that at this point *d*(0, *q*<sub>*l*</sub>) does not depend on *q*<sub>*r*</sub>.

The goal at step $t \in \{1, \dots, K\}$ is to select the $k$-block disparity, denoted, for now, as $s$. We
assume that a disparity map $d(t-1, q_l, q_r)$ has already been computed at step $t-1$. For each
$s \in S$, a predicted image $I_p(t, q_l, q_r, s)$ is computed taking into account $s$ on the $t^{th}$ block and
$d_k(t-1, q_l, q_r)$ for all other blocks:

$$
\mathbf{I}_p(t, q_l, q_r, s) \begin{bmatrix} i_k + \Delta i \\ j_k + \Delta j \end{bmatrix} = \begin{cases} \hat{\mathbf{I}}_l \begin{bmatrix} i_k + \Delta i \\ j_k + \Delta j + d_k(t-1, q_l, q_r) \end{bmatrix} & \text{if } k \neq t \\ \hat{\mathbf{I}}_l \begin{bmatrix} i_k + \Delta i \\ j_k + \Delta j + s \end{bmatrix} & \text{if } k = t \end{cases} \tag{16}
$$

with $(\Delta i, \Delta j)$ spanning $\mathcal{B}$ and $k$ ranging from 1 to $K$.
Compensation transforms $\mathbf{I}_p(t, q_l, q_r, s)$ into $\hat{\mathbf{I}}_r(t, q_l, q_r, s)$ as follows:

$$ \hat{\mathbf{I}}_r(t, q_l, q_r, s) = \mathbf{I}_p(t, q_l, q_r, s) + D_r C_{q_r} (\mathbf{I}_r - \mathbf{I}_p(t, q_l, q_r, s)). \quad (17) $$

Finally $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$ is computed and the best disparity is selected as follows:

$$ d_k(t, q_l, q_r) = \begin{cases} d_k(t - 1, q_l, q_r) & \text{if } k \neq t \\ \arg\min_{s \in \mathcal{S}} J(\hat{\mathbf{I}}_r(t, q_l, q_r, s), \mathbf{I}_r) & \text{if } k = t \end{cases} \quad (18) $$

The DCBM algorithm is summarized in algorithm 2.

**Algorithm 2 DCBM algorithm**

**Input:** $\mathbf{I}_l, \mathbf{I}_r, q_l, q_r$

**Output:** $C_{q_l}(\mathbf{I}_l), C(\mathbf{d}), C_{q_r}(\mathbf{R}), b, \mathcal{J}$

Compute $C_{q_l}(\mathbf{I}_l), \hat{\mathbf{I}}_l$ with (1) and $J(\hat{\mathbf{I}}_l, \mathbf{I}_l)$ with (8) and (9)

Compute $\mathbf{d}(0, q_l)$ with (15) using $\mathbf{I}_p$ defined by (2)

**for all** $t \in \{1...K\}$ **do**

**for all** $s \in \mathcal{S}$ **do**

Compute $\mathbf{I}_p(t, q_l, q_r, s)$ with (16) using $\mathbf{d}(t-1, q_l, q_r)$

Compute $\hat{\mathbf{I}}_r(t, q_l, q_r, s)$ with (17)

Compute $J(\hat{\mathbf{I}}_r(t, q_l, q_r, s), \mathbf{I}_r)$ with (9)

**end for**

Select $\mathbf{d}(t, q_l, q_r)$ with (18) using all $s$-values of $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$

**end for**

Get $\mathbf{d} = \mathbf{d}(K, q_l, q_r)$ and compute $C(\mathbf{d})$

Compute $\mathbf{I}_p$ with (2) using $\mathbf{d}$

Compute $\mathbf{R} = \mathbf{I}_r - \mathbf{I}_p$ and $C_{q_r}(\mathbf{R})$ with (5)

Compute $\hat{\mathbf{I}}_r$ with (6) and $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$ with (9)

Compute $\mathcal{J}$ with (10) using $J(\hat{\mathbf{I}}_l, \mathbf{I}_l)$ and $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$

Compute $b(\mathbf{I}_l, \mathbf{d}, \mathbf{I}_r, q_l, q_r)$ with (7) using $C_{q_l}(\mathbf{I}_l), C(\mathbf{d}), C_{q_r}(\mathbf{R})$

Note that the increased numerical complexity when using DCBM, stems from the necessity, to code and decode a new image, at each block and then each time a new disparity value is considered.
## 5 Fast DCBM algorithm, a suboptimal algorithm with reasonable complexity

Due to the interesting performance of the DCBM algorithm in terms of rate-distortion (see 24), this section proposes a Fast version of this algorithm called FDCBM algorithm. The novelty is that disparity selection is no longer based on the computation of $\hat{I}_r$ with all its pixel values. This section is organized as follows. Considering first the case of blocks having a size of 8×8, subsection 5.1 shows that only 8×8 pixel-values of $\mathbf{R}$ are to be taken into account. Subsection 5.2 derives from the JPEG-codec an explicit formula using these 8×8 pixel-values. Subsection 5.3 derives the FDCBM algorithm. Subsection 5.4 extends this algorithm to some larger blocks.

### 5.1 FDCBM algorithm underlying idea

This section considers that the size of $\mathcal{B}$ is 8×8 and more specifically that the disparity-related blocks are exactly the JPEG-related blocks. Introduce first some new notations. Define $\hat{\mathbf{R}} = D_r C_{q_r}(\mathbf{R})$ the reconstructed residual at the decoder, and $\mathbf{I}_k$ any matrix of size 8×8:

$$ 
\left\{ 
\begin{aligned}
\mathbf{R}_k (\Delta i, \Delta j) &= \mathbf{R} (i_k + \Delta i, j_k + \Delta j) \\
\hat{\mathbf{R}}_k (\Delta i, \Delta j) &= \hat{\mathbf{R}} (i_k + \Delta i, j_k + \Delta j) \\
\|\mathbf{I}_k\|^2 &= \frac{1}{|\mathcal{B}|} \sum_{(\Delta i, \Delta j) \in \mathcal{B}} (\mathbf{I}_k (\Delta i, \Delta j))^2
\end{aligned}
\right. 
\quad (19) 
$$

So as to be consistent with notations defined in Sec. 2, indexes of these 8×8 matrices start from 0: $\Delta i, \Delta j \in \{0, \dots, 7\}$. Note that because of the above block-related assumption, $\hat{\mathbf{R}}_k$ can also be considered as the decoded-encoded 8×8 matrix $\mathbf{R}_k$:

$$ \hat{\mathbf{R}}_k = D_r C_{q_r}(\mathbf{R}_k). \quad (20) $$
Our main claim is that the relevant pixel values are those of $\mathbf{R}_k$, and that $J_k$ measures the mean squared distortions yielded by the compression and decompression of $\mathbf{R}_k$:

$$J_k(\hat{\mathbf{I}}_r, \mathbf{I}_r) = J_k(\mathbf{I}_p + \hat{\mathbf{R}}, \mathbf{I}_p + \mathbf{R}) = J_k(\hat{\mathbf{R}}, \mathbf{R}) = \|D_r C_{q_r}(\mathbf{R}_k) - \mathbf{R}_k\|^2. \quad (21)$$

The first equality is obtained with Eqs. (5) and (6). The second equality uses an additive-invariance property derived from Eq. (8). The third equality is computed using Eqs. (8), (19) and (20).

## 5.2 Using the JPEG-codec strategy

Of the JPEG-codec, this section is only interested in what causes distortions, namely the quantization of the DCT-components:

$$D_r C_{q_r}(\mathbf{R}_k) = \mathrm{DCT}[Q_{q_r}(\mathrm{DCT}[\mathbf{R}_k])], \quad (22)$$

where $Q_{q_r}$ is the 8×8-JPEG-quantizer.

As DCT is an orthogonal transformation, it preserves the L2 norm:

$$\|D_r C_{q_r}(\mathbf{R}_k) - \mathbf{R}_k\|^2 = \|\mathrm{DCT}[D_r C_{q_r}(\mathbf{R}_k)] - \mathrm{DCT}[\mathbf{R}_k]\|^2, \quad (23)$$

Combining Eqs. (22) and (23), a minimized formula of the mean squared distortions is obtained:

$$\|D_r C_{q_r}(\mathbf{R}_k) - \mathbf{R}_k\|^2 = \|Q_{q_r}(\mathrm{DCT}[\mathbf{R}_k]) - \mathrm{DCT}[\mathbf{R}_k]\|^2. \quad (24)$$

The explicit formula uses the following information extracted from the JPEG-codec (see$^{25}$).
211 The DCT of an 8×8 matrix is:

$$ \text{DCT}[\mathbf{I}_k] = T^T \mathbf{I}_k T, \qquad (25) $$

212 where T is an 8×8 orthogonal matrix defined as follows:

$$ T_{\Delta i, \Delta j} = \frac{1}{\sqrt{8}} \cos \left( \pi \frac{(2\Delta j + 1)\Delta i}{16} \right) \times \begin{cases} 1 & \text{if } \Delta i = 0 \\ \sqrt{2} & \text{if } 1 \le \Delta i \le 7 \end{cases} \qquad (26) $$

213 The JPEG quantization table is:

$$ Q = \begin{bmatrix} 16 & 11 & 10 & 16 & 24 & 40 & 51 & 61 \\ 12 & 12 & 14 & 19 & 26 & 58 & 60 & 55 \\ 14 & 13 & 16 & 24 & 40 & 57 & 69 & 56 \\ 14 & 17 & 22 & 29 & 51 & 87 & 80 & 62 \\ 18 & 22 & 37 & 56 & 68 & 109 & 103 & 77 \\ 24 & 35 & 55 & 64 & 81 & 104 & 113 & 92 \\ 49 & 64 & 78 & 87 & 103 & 121 & 120 & 101 \\ 72 & 92 & 95 & 98 & 112 & 100 & 103 & 99 \end{bmatrix}. \qquad (27) $$

214 The JPEG-quantizer transforms an 8×8-matrix into an 8×8-matrix:

$$ Q_{q_r}(\mathbf{I}) = \left[ \text{Round} \left( \frac{\mathbf{I}(\Delta i, \Delta j)}{Q(\Delta i, \Delta j) \alpha(q_r)} \right) Q(\Delta i, \Delta j) \alpha(q_r) \right]_{\Delta i, \Delta j} \qquad (28) $$
215 using a nonlinear mapping transforms $q_r$ into a scaling factor (see$^{26}$):

$$ \alpha(Q) = \begin{cases} \frac{50}{Q} & \text{if } Q \le 50 \\ 2 - \frac{Q}{50} & \text{if } Q > 50 \end{cases} \qquad (29) $$

216 Experimentations have shown that $J_k(\hat{\mathbf{I}}_r, \mathbf{I}_r)$ is not exactly equal to
217 $\|Q_{q_r}(\text{DCT}[\mathbf{R}_k]) - \text{DCT}[\mathbf{R}_k]\|^2$, and the latter depends on $q_l, q_r$ and on the $k$-block disparity, $s$.

218 So the following notation is used:

$$ \tilde{J}_k(q_l, q_r, s) = \|Q_{q_r}(\text{DCT}[\mathbf{R}_k]) - \text{DCT}[\mathbf{R}_k]\|^2. \qquad (30) $$

219 Finally the $k$-block disparity is selected as:

$$ d_k(q_l, q_r) = \arg\min_{s \in \mathbf{S}} \tilde{J}_k(q_l, q_r, s). \qquad (31) $$

220 **5.3 Derived FDCBM algorithm**

221 The FDCBM algorithm is summarized in algorithm 3. It is very similar to the DCBM algo-
222 rithm, the difference is inside the double loop. Instead of computing large scale images, only
223 8×8-matrices are computed and yield $\tilde{J}_k(q_l, q_r, s)$, an approximation of $J_k(\hat{\mathbf{I}}_r, \mathbf{I}_r)$ using Eq. (30).
224 Instead of selecting the $k$-block disparity based on $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$, it is based on the minimization of
225 $\tilde{J}_k(q_l, q_r, s)$.

226 The numerical complexity of FDCBM algorithm is definitely much lower than that of DCBM.
227 It remains higher than BM algorithm, not only because of the complexity of Eq. (30) but also
228 because it takes into account $q_l$ and $q_r$, whereas BM takes into account only $q_l$.
**Algorithm 3 FDCBM algorithm**

**Input:** $\mathbf{I}_l, \mathbf{I}_r, q_l, q_r$

**Output:** $C_{ql}(\mathbf{I}_l), C(d), C_{qr}(\mathbf{R}), b, \mathcal{J}$

Compute $C_{ql}(\mathbf{I}_l), \hat{\mathbf{I}}_l$ with (1) and $J(\hat{\mathbf{I}}_l, \mathbf{I}_l)$ with (8) and (9)

**for all** $k \in \{1...K\}$ **do**

**for all** $s \in S$ **do**

Compute $\mathbf{R}_k$ using $\hat{\mathbf{I}}_l$ and $\mathbf{I}_r$ with (19), (2) and (5)

Compute $\tilde{J}_k(q_l, q_r, s)$ with (30)

**end for**

Select $d_k$ with (31) using all $s$-values of $\tilde{J}_k(s)$

**end for**

Collect $d = (d_1, ..., d_K)$ and compute $C(d)$

Compute $\mathbf{I}_p$ with (2) using $d$

Compute $\mathbf{R} = \mathbf{I}_r - \mathbf{I}_p$ and $C_{qr}(\mathbf{R})$ with (5)

Compute $\hat{\mathbf{I}}_r$ with (6) and $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$ with (9)

Compute $\mathcal{J}$ with (10) using $J(\hat{\mathbf{I}}_l, \mathbf{I}_l)$ and $J(\hat{\mathbf{I}}_r, \mathbf{I}_r)$

Compute $b(\mathbf{I}_l, \mathbf{d}, \mathbf{I}_r, q_l, q_r)$ with (7) using $C_{ql}(\mathbf{I}_l), C(d), C_{qr}(\mathbf{R})$

229 **5.4 Extending the FDCBM algorithm to larger blocks**

230 This section considers the case when the block decomposition yielding the disparity map is not the same than the JPEG-block decomposition. To distinguish them, the former is denoted $\mathcal{B}_k$, (1 ≤ $k$ ≤ $K$, $\mathcal{B}$ as the set of internal displacements), the latter is denoted $\mathcal{B}'_{k'}$, (1 ≤ $k'$ ≤ $K'$, $\mathcal{B}'$ as the set of internal displacements). In general, a block $\mathcal{B}_k$ is likely to have common pixels with several blocks $\mathcal{B}'_{k'}$ and each of these blocks may have common pixels with other blocks $\mathcal{B}_{k''}$.

235 In such a situation, the optimal choice of a disparity $d_k$ depends on the choice of disparities of neighboring blocks, and adapting the FDCBM algorithm seems difficult. Here we assume that each block $\mathcal{B}_k$ can be divided exactly in a finite number of blocks $\mathcal{B}'_{k'}$, and show how FDCBM can easily be extended. For instance when an image is decomposed into 16×16-blocks, each of them covers exactly four 8×8-blocks. And when an image is decomposed into 32×32-blocks, each of them covers exactly sixteen 8×8-blocks.
Let $\mathcal{K}_k$ be the set of indexes indicating the blocks $\mathcal{B}'_{k'}$ that are exactly covering $\mathcal{B}_k$:

$$ \mathcal{B}_k = \bigcup_{k' \in \mathcal{K}_k} \mathcal{B}'_{k'} \qquad (32) $$

The size of $\mathcal{K}_k$ can be computed:

$$ \left\{ \begin{array}{l} K|\mathcal{B}_k| = K'|\mathcal{B}'_{k'}| \\ |\mathcal{B}_k| = |\mathcal{K}_k||\mathcal{B}'_{k'}| \end{array} \right. \Rightarrow |\mathcal{K}_k| = \frac{K'}{K}, \qquad (33) $$

where $|\cdot|$ indicates the size of a set. The first equation is derived from the fact that each view of the considered stereoscopic image is divided into a set of non-overlapping blocks. The second equation is derived from Eq. (32).

The mean squared error defined in Eq. (8) has now two definitions depending on the considered block-decomposition:

$$ J_k(\hat{\mathbf{I}}, \mathbf{I}) = \frac{1}{|\mathcal{B}|} \sum_{(i,j) \in \mathcal{B}_k} (\hat{\mathbf{I}}(i,j) - \mathbf{I}(i,j))^2, \qquad (34) $$

$$ J'_{k'}(\hat{\mathbf{I}}, \mathbf{I}) = \frac{1}{|\mathcal{B}'|} \sum_{(i,j) \in \mathcal{B}'_{k'}} (\hat{\mathbf{I}}(i,j) - \mathbf{I}(i,j))^2. $$

Equation (32) yields a relationship between the two mean squared error functions:

$$ J_k(\hat{\mathbf{I}}, \mathbf{I}) = \frac{1}{|\mathcal{K}_k|} \sum_{k' \in \mathcal{K}_k} J'_{k'}(\hat{\mathbf{I}}, \mathbf{I}). \qquad (35) $$

Subsections 5.1 and 5.2 are applied to the JPEG-block decomposition, resulting in the follow-
ing approximation:

$$J'_{k'}(\hat{\mathbf{I}}_r, \mathbf{I}_r) \approx \tilde{J}_{k'}(q_l, q_r, s), \quad (36)$$

where $s$ is the $k'$-block disparity in the sense of the JPEG-block decomposition.

Eqs. (35) and (36) yield the $k$-block disparity:

$$d_k(q_l, q_r) = \arg \min_{s \in \mathcal{S}} \frac{1}{|\mathcal{K}_k|} \sum_{k' \in \mathcal{K}_k} \tilde{J}_{k'}(q_l, q_r, s). \quad (37)$$

This is the proposed extended FDCBM algorithm.

# 6 Performance evaluation of the proposed FDCBM algorithm

This section analyzes and discusses the simulation results of the developed FDCBM algorithm using synthetic data and stereoscopic image datasets.

## 6.1 Impact on the performance of the proposed explicit formula

First of all, this section proposes to discuss the relevance of the derived Eq. (30) on which the proposed FDCBM algorithm is based. To do so, experiments are conducted on synthetic data to measure the ability of this equation to reduce distortions more than the BM algorithm.

For each $q_r \in \{1, \dots, 99\}$, 200 stereoscopic images of size 256×256 are randomly drawn from independent uniform distributions (here left views are not encoded). On each image, a block is randomly selected and for this block, the BM, DCBM and FDCBM algorithms yield three disparities denoted as $d_{\text{BM}}(q_r, \omega)$, $d_{\text{DCBM}}(q_r, \omega)$, $d_{\text{FDCBM}}(q_r, \omega)$ using $\omega$ ranging from 1 to 200 and $S = \{-14, \dots, 15\}$. For each image and each algorithm, its mean squared distortion is computed
266 and denoted as $J_k(q_r, d_{\text{BM}}(q_r, \omega), \omega)$, $J_k(q_r, d_{\text{DCBM}}(q_r, \omega), \omega)$ and $J_k(q_r, d_{\text{FDCBM}}(q_r, \omega), \omega)$. This experiment confirms that:

267

$$ \left\{ \begin{array}{l} J_k(q_r, d_{\text{DCBM}}(q_r, \omega), \omega) \le J_k(q_r, d_{\text{BM}}(q_r, \omega), \omega) \\ J_k(q_r, d_{\text{DCBM}}(q_r, \omega), \omega) \le J_k(q_r, d_{\text{FDCBM}}(q_r, \omega), \omega) \end{array} \right. $$

268 Moreover, the experiment shows that most often:

$$ J_k(q_r, d_{\text{FDCBM}}(q_r, \omega), \omega) \le J_k(q_r, d_{\text{BM}}(q_r, \omega), \omega) $$

269 To see how $J_k(q_r, d_{\text{FDCBM}}(q_r, \omega), \omega)$ is close to $J_k(q_r, d_{\text{DCBM}}(q_r, \omega), \omega)$ as compared to $J_k(q_r, d_{\text{BM}}(q_r, \omega), \omega)$, we measured an average distortion reduction ratio as follows:

270

$$ \rho(q_r) = \frac{1}{200} \sum_{\omega=1}^{200} \frac{J_k(q_r, d_{\text{BM}}(q_r, \omega), \omega) - J_k(q_r, d_{\text{FDCBM}}(q_r, \omega), \omega)}{J_k(q_r, d_{\text{BM}}(q_r, \omega), \omega) - J_k(q_r, d_{\text{DCBM}}(q_r, \omega), \omega)}. \quad (38) $$

271 Fig. 2 illustrates the behaviour of $\rho(q_r)$ when $q_r$ ranges from 1 to 100. It shows that when $q_r$ is between 15 and 90, on average and compared to the distortions left when using BM algorithm, 272 FDCBM algorithm is able to reduce at least 90% of the distortions that DCBM algorithm is able 273 to reduce. 274

275

## 6.2 Simulation results on stereoscopic images

276

Simulation results are performed on stereoscopic images downloaded from the Middleburry dataset⁵ and 3D LIVE dataset.²⁷ A performance comparison of the FDCBM algorithm with BM algorithm is discussed. Measuring the true performance of an algorithm means evaluating the average visual experience provided by the compressed stereoscopic image at a given bitrate. Subjective evalu-

277

278

279
<figure><img src="image_4.png" /><figcaption>**Fig 2** Average distortion reduction ratio of BM-FDCBM as compared to BM-DCBM on synthetic data as a function of $q_r$.</figcaption></figure>

ation is the most accurate technique and the most demanding. Evaluating with objective quality metrics is a much easier and the design of such metrics is an existing research field as exemplified in Ref. 28. As of now, no objective quality metric has proven to be completely reliable when applied to stereoscopic images.

In this paper, the distortion is measured using the Peak Signal to Noise Ratio (PSNR) using a dB scale. To simplify the experiment, the left view is not compressed, the rate-distortion is measured only on the right view as follows:

$$PSNR = 10 \log_{10} \left( \frac{255^2}{J(\hat{\mathbf{I}}_r, \mathbf{I}_r)} \right), \qquad (39)$$

$$b = \frac{|C(\mathbf{d})| + |C_{q_r}(\mathbf{R})|}{|\mathbf{I}_r|},$$

where b is in bits per pixel (bpp); and pixel-values, on both views, are ranging from 0 to 255.

The lossless coder, C is here an arithmetic coder (see$^{29}$). To reduce the numerical complexity,
<figure><img src="image_5.png" /><figcaption>**Fig 3** Original right view of the "Art" stereoscopic image.</figcaption></figure>

289 the set of quality factor values is reduced to $Q_r = \{5, 10, 15, \dots, 90\}$. The set of all available 290 disparities is $S = \{0, \dots, 120\}$. This choice (on the selected dataset) ensures better performance 291 than when each of the views is encoded in an independent way.

292 As for the sizes of blocks fixed in the disparity prediction process, we use 8×8, 16×16 and 293 32×32 blocks. Note that both views are always decomposed into non-overlapping blocks of same 294 size.

295 The rate-distortion curves, in Fig. 4 confirm the results stated above (subsection 6.1) using 296 "Art" stereoscopic image (original right view is provided by Fig. 3) of 2006 Middlebury-dataset 297 and blocks of size 8×8. Indeed the performance of the proposed FDCBM algorithm is similar to 298 that of DBCM algorithm, which is however better than that of the classical BM algorithm.

299 Fig. 5 provides the original right view of the "Aloe" stereoscopic image extracted from the 300 2006 Middlebury-dataset. Fig. 6 presents the compressed and decompressed "Aloe" right view 301 using BM algorithm on the left side and FDCBM on the right side. For each algorithm, blocks are 302 of sizes 8×8 and $q_r \in Q_r$ is set so that $b = 0.3buch$.
<figure><img src="image_6.png" /><figcaption>**Fig 4** Performance comparison of BM, DCBM and FDCBM algorithms using "Art" stereoscopic image of 2005 Middlebury-dataset.</figcaption></figure>

303 with the original, it appears that the background cloth on right neighborhoods of each vertical leaf
304 is wrongly drawn. The reason may be that these neighborhoods are occluded in the left view. The
305 BM algorithm yields a dotted structure whereas the FDCBM algorithm yields a slightly blurred
306 square texture. From a PSNR-viewpoint, the FDCBM-reconstructed view is closer to the original
307 view (30.14dB) than the BM-reconstructed view (29.5dB).

308 Fig. 7 shows the histograms of, on the left side, the BM-disparity map and, on the right side,
309 the FDCBM-disparity map for the same experiment. More specifically, selected disparity values
310 are sorted into 10 bins, each bin is referred to by its average disparity value on the horizontal
311 axis. The vertical axis indicates the number of blocks for which the disparity value falls into a
312 given bin (the total number of blocks for that image is 2726). Both histograms are right skewed,
313 showing that for most blocks it did not proved useful to consider disparity values greater than 50.
314 A closer look shows that, on the right hand side, the two first columns are slightly bigger and the
<figure><img src="image_7.png" /><figcaption>Fig 5 Original right view of the "Aloe" stereoscopic image.</figcaption></figure>

two following columns are slightly smaller. This means that for this specific image, on average
FDCBM algorithm tends to select smaller disparity values than BM algorithm.

As for numerical complexity, FDCBM algorithm (consuming 17 seconds) is 3 388 times
quicker than DCBM algorithm (consuming 4 hours) and 6.8 times slower than BM algorithm
(consuming 2.5 seconds). This was measured on the "Aloe" stereoscopic image with block of
8 × 8 size using Matlab in a Windows environment on a computer using one processor with four
cores at a frequency of 3.7GHz.

Simulation results provided in Fig. 8 have been conducted on "Art" stereoscopic image (original right view is shown in Fig. 3). FDCBM algorithm is implemented with different $q_r$ values yielding three different rate-distortion curves shown on the left side. The green and right-most curve is obtained with 8×8 blocks. The red and middle curve is obtained with 16×16 blocks. The blue and left-most curve is obtained with 32×32 blocks. As we can see, using blocks of greater size, reduces the bitrate and tends to move the rate-distortion curve leftwards and downwards.

When addressing a specific need, in terms of expected PSNR or of allowed bitrate, it makes
<figure><img src="image_8.png" /><figcaption>**Fig 6** On the left side: reconstructed "Aloe" right view with BM algorithm at *b* = 0.3bpp (*PSNR* = 29.5dB); On the right side: reconstructed "Aloe" right view with FDCBM algorithm at *b* = 0.3bpp (*PSNR* = 30.14dB).</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Fig 7** Histogram of the disparity map yielded at *b* = 0.3bpp using: on the left side, the BM-algorithm; and, on the right side, the FDCBM-algorithm.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>**Fig 8** FDCBM rate-distortion curves for the "Art" stereoscopic image, using 8×8-blocks (green and left-most curve), 16×16-blocks (red and middle curve), 32×32-blocks (blue and right-most curve); and BM (red and bottom curve).</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>**Fig 9** Higher convex envelop curve generated with the three-block-size, rate-distortion curves, using FDCBM (blue and top curve).</figcaption></figure>

sense to use the most appropriate block size to meet the request. So when comparing BM with FDCBM, it is more relevant to compare, the two higher convex envelopes generated by each three rate-distortion curves, than to compare the rate-distortion curves one by one. These two envelopes are illustrated in Fig. 9 where the blue top curve is obtained with FDCBM algorithm and the red bottom curve is obtained with BM algorithm. At low bitrate (below 0.2bpp), BM is better performing, whereas at higher bitrate, FDCBM algorithm is better performing.
The Bjøntegaard metric³⁰ is used here to quantify the increase in performance of FDCBM as compared to BM. Based on four rate-distortion points for each algorithm (roughly [0.3, 0.4, 0.5, 0.6]bpp), it computes, an average PSNR increase, or, an average bitrate decrease. As for the "Art" stereoscopic image, FDCBM algorithm yields on average a PSNR increase of 0.78dB.

All 30 stereoscopic images extracted from the 2005 and 2006 Middlebury-database are compressed and decompressed using BM and FDCBM algorithms and using blocks of sizes 8×8, 16×16 and 32×32. For each stereoscopic image, two corresponding higher convex envelopes are computed. Four rate-distortions points from each envelope are extracted and used by the Bjøntegaard metric to provide an average PSNR increase, or, an average bitrate decrease. These measures are shown in Table 1. To simplify its reading, the stereoscopic images have been sorted by their increase in PSNR-performance. This table shows that, on average, for all stereoscopic images, FDCBM is better performing than BM, the difference ranges from 0.17dB up to 1.28dB. It seems difficult to understand why this difference is higher for some images and lower on other images. For instance "Cloth3" and "Cloth4" appear at both ends of the table and yet have similar appearance. The same comment applies to "Baby1" and "Baby3". And both "Midd1", "Midd2" and "Lampshade1", "Lampshade2" have similar appearance and yet each pair has quite different performance increases. It is interesting to note that the stereoscopic image having the least PSNR-performance increase (+0.17dB), namely "Plastic", is having a rather important bitrate decrease (−15.7%). Table 2 provides other simulation results performed on 3D LIVE database.²⁷

The increase in performance of all 48 stereoscopic images of FDCBM as compared to BM is also shown in Fig. 10. More specifically, 10 bins have been considered ranging from +0.25dB up to +1.25dB in terms of increase in terms of PSNR performance of FDCBM as compared to BM.
<table><caption>**Table 1** Performance comparison between FDCBM and BM algorithms using the Bjøntegaard metric and 2005 and 2006 Middlebury-database.</caption><thead><tr><td>Image</td><td>ΔPSNR (dB)</td><td> (%)</td></tr></thead><tbody><tr><td>Plastic</td><td>+0.17</td><td>-15.73</td></tr><tr><td>Cloth3</td><td>+0.31</td><td>-7.44</td></tr><tr><td>Midd1</td><td>+0.31</td><td>-4.79</td></tr><tr><td>Cloth1</td><td>+0.34</td><td>-9.08</td></tr><tr><td>Laundry</td><td>+0.37</td><td>-5.66</td></tr><tr><td>Computer</td><td>+0.39</td><td>-6.3</td></tr><tr><td>Baby1</td><td>+0.39</td><td>-8.17</td></tr><tr><td>Baby2</td><td>+0.42</td><td>-9.35</td></tr><tr><td>Wood1</td><td>+0.43</td><td>-8.9</td></tr><tr><td>Rocks2</td><td>+0.44</td><td>-9.89</td></tr><tr><td>Books</td><td>+0.46</td><td>-7.93</td></tr><tr><td>Aloe</td><td>+0.53</td><td>-11.7</td></tr><tr><td>Lampshade1</td><td>+0.54</td><td>-5.09</td></tr><tr><td>Rocks1</td><td>+0.56</td><td>-12.43</td></tr><tr><td>Bowling2</td><td>+0.57</td><td>-9.86</td></tr><tr><td>Midd2</td><td>+0.58</td><td>-10.51</td></tr><tr><td>Drumsticks</td><td>+0.58</td><td>-8.85</td></tr><tr><td>Dolls</td><td>+0.59</td><td>-10.65</td></tr><tr><td>Moebius</td><td>+0.65</td><td>-11.44</td></tr><tr><td>Cloth2</td><td>+0.66</td><td>-12.68</td></tr><tr><td>Baby3</td><td>+0.67</td><td>-12.74</td></tr><tr><td>Wood2</td><td>+0.72</td><td>-9.34</td></tr><tr><td>Monopoly</td><td>+0.75</td><td>-13.56</td></tr><tr><td>Cloth4</td><td>+0.76</td><td>-17.12</td></tr><tr><td>Art</td><td>+0.78</td><td>-11.36</td></tr><tr><td>Bowling1</td><td>+0.89</td><td>-14.47</td></tr><tr><td>Dwarves</td><td>+1.06</td><td>-17.48</td></tr><tr><td>Flowerpots</td><td>+1.12</td><td>-14.52</td></tr><tr><td>Lampshade2</td><td>+1.23</td><td>-22.76</td></tr><tr><td>Mean</td><td>+0.62</td><td>-11.38</td></tr></tbody></table>

Each bar is associated to a specific bin, and its height indicates the number of stereoscopic images, having an increase in PSNR performance of roughly the amount indicated on the bin. The average increase in PSNR performance is 0.54dB.
<table><caption>**Table 2** Performance comparison between FDCBM and BM algorithms using the Bjøntegaard metric and 3D LIVE-database.</caption><thead><tr><td>Image</td><td>ΔPSNR (dB)</td><td> (%)</td></tr></thead><tbody><tr><td>im20</td><td>+0.18</td><td>-7,32</td></tr><tr><td>im8</td><td>+0.21</td><td>-5,85</td></tr><tr><td>im29</td><td>+0.22</td><td>-7.06</td></tr><tr><td>im13</td><td>+0.25</td><td>-7.43</td></tr><tr><td>im22</td><td>+0.29</td><td>-9.48</td></tr><tr><td>im18</td><td>+0.34</td><td>-7.52</td></tr><tr><td>im3</td><td>+0.36</td><td>-11.14</td></tr><tr><td>im14</td><td>+0.37</td><td>-12.23</td></tr><tr><td>im16</td><td>+0.38</td><td>-11.47</td></tr><tr><td>im21</td><td>+0.42</td><td>-15.13</td></tr><tr><td>im7</td><td>+0.45</td><td>-9.47</td></tr><tr><td>im17</td><td>+0.51</td><td>-17.75</td></tr><tr><td>im15</td><td>+0.53</td><td>-15.92</td></tr><tr><td>im10</td><td>+0.55</td><td>-14.22</td></tr><tr><td>im24</td><td>+0.58</td><td>-14.22</td></tr><tr><td>im26</td><td>+0.61</td><td>-17.23</td></tr><tr><td>im5</td><td>+0.62</td><td>-18.26</td></tr><tr><td>im27</td><td>+0.73</td><td>-19.38</td></tr><tr><td>Mean</td><td>+0.42</td><td>-12.74</td></tr></tbody></table>

361 **7 Conclusion**

A new block-based disparity estimation technique called FDCBM algorithm for Fast Disparity Compensated Block Matching strategy is proposed. The purpose of this work is not to be competitive with stereoscopic image\video standards, but to first show the feasibility of the proposed approach as a proof of the concept. Where the classical technique selects each disparity so that the predicted image resembles most the right view, the proposed technique computes for each disparity the compensated image, and the selected disparity is the one yielding the highest similarity between the compensated image and the right view. The computation is done with an analytic expression derived here from the JPEG-codec. To reduce the numerical complexity, these computations are fed using only the considered block pixel-values.
<figure><img src="image_12.png" /><figcaption>**Fig 10** Histogram of the increase in average PSNR-performance of FDCBM as compared to BM, in terms of the number of stereoscopic images among the 30 extracted from the 2005 and 2006 Middlebury-database.</figcaption></figure>

Tested on the 48 stereoscopic images extracted from the 2005-2006 Middlebury-dataset and 3D LIVE-dataset, FDCBM algorithm is performing better than the classical Disparity Compensated Compression algorithm using a Block-Matching disparity estimation technique. As compared to the latter, the increase in performance, at same bitrate, is ranging, depending on the stereoscopic image, from 0.18dB up to 1.3dB with an average of 0.54dB, (performance being here measured using the Peak Signal to Noise Ratio).

The underlying idea of this paper is not to replace the residual error encoding methods in the stereoscopic image/video standards by JPEG encoding but rather to exploit the quantization parameters and tables, as specified in the standards, to better choose the disparities to improve the compensated view quality. Indeed, the residual error coding is traditionally based on an orthogonal
transformation followed by a quantization process controlled by some parameters associated to quantization tables which need to be studied in future work. Moreover, only equal size blocks have been considered to show the interest of the proposed strategy. Of course, blocks of variable size give better performance and will be investigated in the near future.

### References

1. C. Soares and E. Simao, *Immersive Multimedia in Information Revolution. Trends, Experiences, and Perspectives in Immersive Multimedia and Augmented Reality*, IGI Global, Pennsylvania, United States (2019).

2. R. Corda, D. Giusto, A. Liotta, et al., “Recent advances in the processing and rendering algorithms for computer-generated holography,” *Electronics* **8**(5), 1–17 (2019).

3. K. Nam, P. Anh-Hoang, E. Munkh-Uchral, et al., “3D Display Technology,” *Display and Imaging* **1**, 73–95 (2013).

4. Y. Frauel, E. Tajahuerce, O. Matoba, et al., “Comparison of passive ranging integral imaging and active imaging digital holography for three-dimensional object recognition,” *Applied Optics* **43**, 452–462 (2004).

5. D. Scharstein and C. Pal, “Learning conditional random fields for stereo,” in *IEEE Conference on Computer Vision and Pattern Recognition*, 1–8 (2007).
http://vision.middlebury.edu/stereo/data/.

6. F. Dufaux, B. Pesquet-Popescu, and M. Cagnazzo, *Emerging Technologies for 3D Video: Creation, Coding, Transmission and Rendering*, Wiley Publishing, 1st ed. (2013).

7. P. F. M. B. Schenkel, C. Luo and F. Wu, “Joint decoding of stereo jpeg image pairs,” in *IEEE International Conference on Image Processing*, 2633–2636 (2010).
403

8 A. Ortis and S. Battiato, "A new fast matching method for adaptive compression of stereo-scopic images," in *Three-Dimensional Image Processing, Measurement (3DIPM), and Applications 2015, San Francisco, California, USA, February 10-12, 2015*, 93930K (2015).

404

405

406

9 U. Ahlvers, U. Zölzer, and S. Rechmeier, "Fft-based disparity estimation for stereo image coding," *Proceedings 2003 International Conference on Image Processing (Cat. No.03CH37429) 1*, 1-761 (2003).

407

408

409

10 H. Schwarz, C. Bartnik, S. Bosse, et al., "3D video coding using advanced prediction, depth modeling, and encoder control methods," in *Picture Coding Symposium*, 1-4 (2012).

410

411

11 Shiping Li, Mei Yu, Gangyi Jiang, et al., "Approaches to h.264-based stereoscopic video coding," in *Third International Conference on Image and Graphics (ICIG'04)*, 365-368 (2004).

412

413

12 P. Hanhart, M. Rerabek, P. Korshunov, et al., "Subjective evaluation of HEVC intra coding for still image compression," tech. rep., [JCT-VC contribution] AhG4 (2013).

414

415

13 W. Woo and A. Ortega, "Stereo image compression with disparity compensation using the MRF model," in *Visual Communications and Image Processing, 2727*, 1-14 (1996).

416

417

14 M. Flierl, A. Mavlankar, and B. Girod, "Motion and disparity compensated coding for multi-view video," *IEEE Transactions on Circuits and Systems for Video Technology*, 1474-1484 (2007).

418

419

420

15 A. Kadaikar, G. Dauphin, and A. Mokraoui, "Sequential block-based disparity map estimation algorithm for stereoscopic image coding," *Elsevier journal, Signal Processing: Image Communication* (2015).

421

422

423

16 A. Kadaikar, G. Dauphin, and A. Mokraoui, "Joint disparity and variable size-block optimization algorithm for stereoscopic image coding," *Elsevier journal, Signal Processing: Image Communication* (2015).
424

mization algorithm for stereoscopic image compression,” *Elsevier journal, Signal Processing: Image Communication* (2017).

425

426

17 G. Dauphin, M. Kaaniche, and A. Mokraoui, “Block dependent dictionary based disparity compensation for stereo image coding,” in *IEEE International conference on image processing*, ICIP, 1–5 (2015, Québec City Canada).

427

428

429

18 G. Shen, W. Kim, A. Ortega, et al., “Edge-aware intra prediction for depth-map coding,” in *2010 IEEE International Conference on Image Processing*, 3393–3396 (2010).

430

431

19 Y. Chen, M. M. Hannuksela, L. Zhu, et al., “Coding techniques in multiview video coding and joint multiview video model,” in *2009 Picture Coding Symposium*, 1–4 (2009).

432

433

20 T. Frajka and K. Zeger, “Residual image coding for stereo image compression,” *Optical Engineering* **42**, 182–189 (2003).

434

435

21 G. K. Wallace, “The jpeg still picture compression standard,” *IEEE Trans. on Consum. Electron.* **38**, xviii–xxxiv (1992).

436

437

22 W. Hachicha, M. Kaaniche, A. Beghdadi, et al., “Efficient inter-view bit allocation methods for stereo image coding,” *IEEE Transactions on Multimedia* **17**, 765–777 (2015).

438

439

23 R. Pan, Z.-X. Hou, and Y. Liu, “Fast algorithms for inter-view prediction of multiview video coding,” *Journal of Multimedia* **6**, 191–201 (2011).

440

441

24 I. Kadri, G. Dauphin, and A. Mokraoui, “Stereoscopic image coding performance using disparity-compensated block matching algorithm,” in *IEEE International Conference on Signal Processing: Algorithms, Architectures, Arrangements, and Applications, SPA*, 1–5 (2019).

442

443

444
445

25 CCIT, "Information technology-digital compression and coding of continuous-tone still images-requirements and guidelines," Tech. Rep. T.81, The International Telegraph and Telephone Consultative Committee CCIT (1992).

446

447

448

26 L. Alam, P. K. Dhar, M. R. Hasan, et al., "An improved JPEG image compression algorithm by modifying luminance quantization table," *International Journal of Computer Science and Network Security (IJCSNS)* **17**, 200–208 (2017).

449

450

451

27 http://live.ece.utexas.edu/research/quality/live_3dimage_phase1.html.

452

453

28 A. Benoit, P. L. Callet, P. Campisi, et al., "Using disparity for quality assessment of stereo-scopic images," in *15th IEEE International Conference on Image Processing*, 15th IEEE International Conference on Image Processing, 389–392 (2008).

454

455

456

29 P. G. Howard and J. Vitter, "Arithmetic coding for data compression," *Proceedings of the IEEE* **82**, 857–865 (1994).

457

458

30 G. Bjøntegaard, "Calculation of average PSNR differences between RD-curves," document VCEG-M33, ITU-T VCEG Meeting, Austin, Texas, USA (2001).

459