## 2 Related Work
### Lagrange Optimization and Lagrange Multiplier Selection  
The Lagrange optimization technique provides a systematic way to solve the constrained RDO problem, which aims at selecting the optimal coding parameter that minimizes the overall distortion measure subject to a given target bitrate restriction. More details on Lagrange optimization technique have been discussed in [16; 20; 36]. This technique is well known in optimization problems where the cost and objective functions are continuous and differentiable. [PERSON]'s contribution [37] demonstrated that the Lagrange optimization technique could also be used for discrete optimization problems, with no loss of optimality if a solution  
Figure 1: Block diagram of the ENH-MC-EZBC codec system model. exists with the required budget; i.e., as long as there exists a point in the convex hull that meets the required budget. Let {Para} denote the coding parameter set, including motion estimation, mode decision, MCTF decomposition levels, etc. For mathematical convenience, the rate control problem can be formulated as: Minimize the distortion D, subject to a target rate \(\mathrm{R_{T}}\):  
\[\left\{\mathrm{Para}\right\}_{\mathrm{opt}}=\arg\min_{\{\mathrm{Para}\}}\mathrm{ D}=\arg\min_{\{\mathrm{Para}\}}\sum_{i=1}^{\mathrm{K}}\mathrm{d}_{i}\ \ \ \mathrm{s.t.}\ \ \sum_{i=1}^{\mathrm{K}}\mathrm{r}_{i}\leq \mathrm{R_{T}}, \tag{1}\]  
where \(\mathrm{d}_{i}\) and \(\mathrm{r}_{i}\) are the distortion and bitrate for the \(i\)th \((i=1,2,\cdots\mathrm{K})\) coding unit, respectively; \(\mathrm{K}\) is the total number of coding units involved and \(\mathrm{R_{T}}\) the available bitrate constraint. In view of the Lagrange optimization, the above constrained optimization problem (1) can be converted into an unconstrained form as:  
\[\left\{\mathrm{Para}\right\}_{\mathrm{opt}}=\arg\min_{\{\mathrm{Para}\}} \mathrm{J}=\arg\min_{\{\mathrm{Para}\}}\left(\mathrm{D}+\lambda\mathrm{R} \right)=\arg\min_{\{\mathrm{Para}\}}\sum_{i=1}^{\mathrm{K}}\left(\mathrm{d}_{ i}+\lambda\mathrm{r}_{i}\right), \tag{2}\]  
where \(\mathrm{J}=\mathrm{D}+\lambda\mathrm{R}\) is the Lagrange cost function, and \(\lambda\) is the so-called Lagrange multiplier that weights the relative importance between \(\mathrm{d}_{i}\) and \(\mathrm{r}_{i}\). The optimal coding parameter set for all coding units can be determined by minimizing the Lagrange cost function as expressed in Equation (2). Consequently, how to determine \(\lambda\) becomes a key problem in Lagrange optimization. To have a better solution to the unconstrained problem, much effort has been placed on the research of the Lagrange multiplier selection. One may attain the \(\lambda\) using bisection search [38; 39]. In RDO for video coding, however, a more computationally efficient approach is usually favorable to determine the Lagrange multiplier. Rather than empirically solving the problem of Lagrange multiplier selection as in [38; 39], the \(\lambda\) in video coding can be determined using an R-D function. Due to the convexity of the R-D curve, the optimal slope \(\lambda\) matched to the desired R can be easily obtained using standard convex search techniques [24; 40]. For each coding unit, the point on the R-D curve that minimizes the Lagrange cost is that point at which the line of absolute slope \(\lambda\) is tangent to the convex hull of the R-D curve. Note that the R-D curve is convex and non-increasing in video coding, and if we assume that both R and D are differentiable everywhere, the minimum of the Lagrange cost function \(\mathrm{J}\) is given by setting its derivative to zero, i.e. :  
\[\frac{\partial\mathrm{J}}{\partial\mathrm{R}}=\frac{\partial\mathrm{D}}{ \partial\mathrm{R}}+\lambda=0, \tag{3}\]  
which yields:  
\[\lambda=-\frac{\partial\mathrm{D}}{\partial\mathrm{R}}\bigg{|}_{\mathrm{R}= \mathrm{R}_{\mathrm{T}}}. \tag{4}\]  
where \(\mathrm{R_{T}}\) is the target bitrate.