6.2 Geometric modeling of depth images
6.2.1 Overview of the depth image coding algorithm
In this section, we present a novel approach for depth image coding using the piecewiselinear functions mentioned in Section 6.1. The concept followed is to approximate the image content with modeling functions. In our framework, we use two classes of modeling functions: a class of piecewiseconstant functions and a class of piecewiselinear functions. For example, flat surfaces that show smooth regions in the depth image can be approximated by a piecewiseconstant function. Similarly, planar surfaces of the scene like the ground plane and walls, appear as regions of gradually changing grey levels in the depth image. Hence, such a planar region can be approximated by a single linear function. To identify the location of these surfaces in the image, we employ a quadtree decomposition (see Figure 6.2), which recursively divides the image into variablesize blocks, i.e., nodes of different size, according to the degree of decomposition.
Figure 6.2 Example of quadtree decomposition. Each block, i.e., nodes, of the quadtree is approximated by one modeling function.

In some cases, the depth image within one block can be approximated with one modeling function. If no suitable approximation can be determined for the block, it is subdivided into four smaller blocks. To prevent that too many small blocks are required along a discontinuity, we divide the block into two regions separated by a straight line. Each of these two regions is coded with an independent function. Consequently, the algorithm chooses between four modeling functions for each leaf as follows.
 Modeling function _{1}: This function approximates the block content with a constant function.
 Modeling function _{2}: This function approximates the block content with a linear function.
 Modeling function _{3}: This function subdivides the block into two regions separated by a straight line and approximates each region with a constant function (a wedgelet function);
 Modeling function _{4}: This function subdivides the block into two regions separated by a straight line and approximates each region with a linear function (a platelet function);
The selection of a particular modeling function is based on a ratedistortion criterion that is described in Section 6.3.1. This criterion tradesoff the distortion and rate of the individual functions.
6.2.2 Modelingfunction definitions
In this section, we define the four different modeling functions _{j}, for j {1,2,3,4}, used to approximate each quadtree block.
To model the depth signal within each block, we focus on finding a compression scheme that can compactly represent smooth blocks as well as boundaries (contours) of objects. First, to approximate smooth blocks, we employ a simple constant function _{1}(x,y) = α_{0}. Second, to approximate gradually changing object surfaces, we use a piecewiselinear function _{2}, which defined by
 (6.1) 
Third, to properly approximate blocks containing sharp edges, we segment those blocks into two regions A and B divided by a straight line of arbitrary direction. Each region is subsequently approximated by one modeling function. To define the position and direction of the subdivisionline, we connect two pixels, P_{1} and P_{2}, located at two different sides of the block. For coding the key parameters of this line, instead of saving the coordinates of both marker points, we use two indexes i_{1} and i_{2} addressing the location of P_{1} and P_{2}. The index is defined such that all pixels directly surrounding the block are scanned in a clockwise fashion (see Figure 6.3).

To determine if a pixel belongs to region A or B, we use a numerical test known as the orientation test in computational geometry applications.
The two resulting regions A and B can be approximated by either a wedgelet function, or a platelet function. A wedgelet function is composed of two piecewiseconstant functions over two regions A and B, separated by a straight line, and can be defined as
 (6.2) 
Similarly, a platelet function is composed of two planar surfaces covering two different regions and separated by a straight edge (waterfall), and is defined by
 (6.3) 
Figure 6.4 depicts example patterns for each modeling function _{1}, _{2}, _{3} and _{4}.
Let us now specify the computation of the function coefficients.
6.2.3 Estimation of model coefficients
The objective of the estimation step is to calculate the coefficients of the modeling functions subject to a constraint. We employ a constraint that minimizes the approximation error between the original depth signal in a block and the corresponding approximation. Specifically, the approximation error is the Mean Squared Error (MSE) over the block where the model applies to. Let us divide the estimation of the modeling function into two sections: one for the constant functions, and one for the linear functions.
A. Coefficient estimation for modeling the constant functions _{1} and _{2}.
For _{1}(x,y) = α_{0}, only one coefficient α_{0} has to be computed. Practically, the coefficient α_{0} that minimizes the MSE between f and _{1} simply corresponds to the mean value of the original data block, which leads to the computation of α_{0} = ∑ _{x,yS}f(x,y).
For _{2}, the function should approximate blocks that contain a gradient. In order to determine the three coefficients β_{0}, β_{1} and β_{2} of the linear function _{2}(x,y) = β_{0} + β_{1}x + β_{2}y, a leastsquares optimization is used. This optimization minimizes the sum of squared differences between the depth image f(x,y) and the proposed linear model. Accordingly, coefficients β_{0}, β_{1} and β_{2} are determined such that the error
 (6.4) 
is minimized, where n denotes the node size expressed in pixels. This error function e_{2}(β_{0},β_{1},β_{2}) is minimal when the gradient function crosses zero, hence ∇e_{2} = 0. When taking the partial derivatives with respect to β_{0},β_{1} and β_{2} of this equation, we find a set of linear equations ^{1} specified by
 (6.5) 
with
 (6.6) 
Since the matrix at the left side of the equation system is constant, it is possible to precompute and store the inverse for each size of the square (quadtree node). This enables to compute the coefficients β_{0},β_{1},β_{2} with a simple matrix multiplication.
B. Coefficient estimation for modeling the linear functions _{3} and _{4}.
For the wedgelet _{3} and platelet _{4} functions, we have to determine not only the model coefficients, but also the separation line. For each model, we aim at approximating the depth value f(x,y) with two functions in the supporting areas A and B. Each area is delineated by a subdividing line P_{1}P_{2}, as defined by points P_{1} and P_{2} (see Figure 6.3). The best set of coefficients for the wedgelet _{3} and platelet _{4} functions are those coefficient values that minimize the approximation errors
 (6.7) 
respectively. These minimizations cannot be solved directly for the following reason. Without knowing the subdivision boundary between the two regions, it is not possible to determine the model coefficients. On the other hand, it is not possible to identify the subdivision line as long as the region coefficients are unknown. To overcome this mutual dependence, we first identify the separation line. For this reason, the coefficient estimation is initialized by testing every possible line that divides the block into two areas. This step provides a candidate subdivision line P_{1}^{c}P_{2}^{c} and two candidate regions A^{c} and B^{c}. Subsequently, the wedgelet and platelet coefficients are computed over the candidate regions using the average pixel value and a leastsquares minimization, respectively. At the end of the exhaustive search for each function _{3} and _{4}, the best fitting model is selected. The major advantage of this technique is that it leads to the optimal set of coefficients that minimizes the leastsquares error between the model and the image block.
Table 6.1 shows a summary of possible modeling functions of the previous subsections to approximate each block of the quadtree and their corresponding coefficientestimation techniques.
Table 6.1 Summary of modeling functions and their corresponding coefficientestimation techniques. 
^{1}To derive this equation, the following properties of series are needed: ∑ _{i=1}^{n}i = and ∑ _{i=1}^{n}i^{2} = , where i takes the parameter x or y.