# On Alpha-Expansion-Based Graph-Cut Optimization for Decoder-Side Depth Estimation
## 2 State of the Art in Alpha-Expansion-Based Graph-Cut Optimization  
Depth estimation is often based on minimizing a cost function [11]. Typically, the cost function can be simplified to  
\[E\left(\overline{d}_{p}\right)=\sum\
olimits_{p\in\mathbb{P}}D_{p}\left( \overline{d}_{p}\right)+\sum\
olimits_{p\in\mathbb{P}}\sum\
olimits_{q\in \mathbb{Q}}V_{p,q}\left(\overline{d}_{p},\overline{d}_{q}\right), \tag{1}\]  
where \(\mathbb{P}\) is the set of all points of the input view, \(p\) is a point of the input view, \(\overline{d}_{p}\) is the currently considered depth of a point \(p\), \(D_{p}\) is the data term that represents the cost of assigning the depth \(\overline{d}_{p}\) to the point \(p\), \(\mathbb{Q}\) is the set of points in the neighborhood of the point \(p\), \(q\) is a point in the neighborhood of the point \(p\), \(\overline{d}_{q}\) is the currently considered depth of a point \(q\), and \(V_{p,q}\) is the smoothness term that represents the intra-view discontinuity cost of assignment of the depth \(d_{p}\) to the point \(p\) and depth \(d_{q}\) to the point \(q\). The data term \(D_{p}\) establishes a correspondence between neighboring views, typically by calculating the sum of absolute differences between color values of point \(p\) and its corresponding point in a neighboring view for the considered depth \(\overline{d}_{p}\). This metric can be replaced or computed within a small window to minimize noise influence [16]. The smoothness term \(V_{p,q}\) deals with surfaces lacking texture. Its discontinuity model is based on depth similarity:  
\[V_{p,q}\Big{(}\overline{d}_{p},\overline{d}_{q}\Big{)}=\beta_{0}\cdot\Big{|} \overline{d}_{p}-\overline{d}_{q}\Big{|}, \tag{2}\]  
where \(\beta_{0}\) is the smoothing coefficient provided by the user or calculated from camera parameters [4], \(\overline{d}_{p}\) is the currently considered depth of a point \(p\), and \(\overline{d}_{q}\) is the currently considered depth of a point \(q\). This formulation aims to estimate smooth depth on scene objects. The \(\beta_{0}\) coefficient sometimes is also dependent on the similarity between neighboring points \(p\) and \(q\)[17]. Nevertheless, this way, \(V_{p,q}\) becomes prone to the effects of compression of input data, as blurred edges in processed video can negatively influence the accuracy of the performed optimization. Additional terms can be included in (1) to ensure inter-view [11; 15] and temporal [18] consistencies. A final solution for \(E\Big{(}\overline{d}_{p}\Big{)}\), i.e., the assignment of one of available depth values to all points of input views, can be estimated using a relevant optimization method. One of the most common among these are graph cut-based methods [19], commonly used for binary problem optimization in image processing. Each image point becomes a node in a graph, with edges representing the cost function. The algorithm finds the optimal cut, which assigns nodes to labels in a way that minimizes the cost function. For multi-label segmentation, solutions are obtained through a series of consecutive optimizations. As can be seen above, the depth estimation process requires multi-label optimization, where each depth level is represented as a label. The two primary methods for minimizing multi-label problems are the alpha-beta swap and alpha-expansion [19]. In the alpha-beta swap, the graph cut algorithm iterates through all pairs of labels \(\alpha\) and \(\beta\), resulting in a large number of optimizations (\(size(d)^{2}\)) required. In the alpha-expansion method, during each iteration, the graph cut algorithm assigns a label \(\alpha\) or retains the current label (referred to as a non-\(\alpha\) label). For instance, if points are initially labeled with label '0' in the first iteration, each point in the first optimization is assigned either label '0' or another label '1'. Subsequently, points are assigned to further labels or retain the previous labeling (i.e., '0' or '1'). This method requires only \(size(d)\) iterations.