# On Alpha-Expansion-Based Graph-Cut Optimization for Decoder-Side Depth Estimation
## 3 The Proposed Method
### Second-Cycle Label Offset  
As shown in other works [14], at least two global cycles of graph cut optimization are required to provide satisfactory quality of estimated depth maps. The second cycle removes a noticeable number of erroneous values, especially in areas which were occluded in some views. Fortunately, the increase of quality when the third cycle is used is negligible [14], so the further increase of optimization time is not required. The necessity of performing a second cycle was also proven with subjective quality measurements performed by MPEG Video Coding experts. It led to using two cycles in the evaluations of the DSDE compression scheme in coding performed by MIV. Therefore, in a hierarchical alpha-expansion approach used in depth estimation for immersive video, it is also necessary to perform two coarse global cycles for every \(n\)-th of available depth values (so the cycle shown in Figure 2A is performed twice). Then, refinement iterations examine \(\pm n/2\) of adjacent depth values to the values acquired from the first two cycles. Such a hierarchical scheme is still less complex than the basic alpha-expansion. Nevertheless, the additional cycle requires a significant amount of additional time for the depth estimation, which is already the most time-consuming part of immersive video decoding.  
In our proposal, assuming that coarse cycles are done for every \(n\)-th of available depth values, we offset by \(n/2\) the initial depth value from which the second coarse global cycle is being performed. For instance, if \(n\) would be equal to 4, then the second cycle would start from depth level '2', instead of '0'. Therefore, \(\overline{d}_{p}\) in the cycle \(c\) is a set defined as  
\[\overline{d}_{p}\in\left\{\begin{matrix}\{nk:k\in\mathbb{N}\bigwedge nk<N\}& ifc=0\\ \{nk+n/2:k\in\mathbb{N}\bigwedge(nk+n/2)<N\}&ifc=1\end{matrix}\right. \tag{5}\]  
With the proposed second-cycle label offset, the time required to estimate depth is noticeably decreased. If \(n\) is equal to 4, then the number of depth levels to be examined is the same as it would be for \(n\) equal to 2 in traditional approach (as every second depth label was already examined in two first cycles). Moreover, for \(n=2\) there is no need to perform any refinement iterations, as all depth values were already examined for all segments after two coarse iterations.  
Using the offset which is a result of dividing \(n\) by odd values (e.g., offset by \(n/3\)) would result in non-optimal depth values to be checked in the second coarse cycle, as these values would not be evenly distributed between values for the first cycle. It would negatively influence the refinement cycle, so the values to be checked would not be \(\pm n/2\). For example, for \(n=4\), \(\{-1,\ 3\}\), the largest distance from the initial depth would increase from 2 to 3. The larger this distance is, the worse the results of the optimization.  
In addition, as our results have shown, increasing \(n\) negatively influences the quality of estimated depth maps (Section 4.2). Therefore, this proposal is beneficial both in terms of the quality and time of estimation, as only a small number of depth values is examined in refinement cycles. Naturally, these considerations are true only if we assume that the first two cycles are performed for all depth levels, as was explained at the beginning of this section.