7.3  Hierarchical search optimization

The guiding principle of the hierarchical optimization is to perform a recursive, coarse-to-fine, search of the optimal quantization setting. The algorithm is summarized as follows. First, a search over a limited number of quantizer candidate settings (qt,qd) is performed. Practically, we employ nine candidates shown as black R-D points and organized them in a search pattern, as illustrated by Figure 7.3. Second, the algorithm selects the candidate with the lowest rendering distortion that satisfies the maximum bit-rate constraint. The search range is then refined and the process is recursively performed by using the selected quantizer set as an initialization, similar to the well-known Three-Step Search in motion estimation [46]. The minimum corresponds to the lowest distortion point after the last recursion.

This technique has two advantages. First, the hierarchical set-up of the search significantly reduces the computational complexity by reducing the possible amount of quantizer candidate settings. Second, by employing an appropriate search pattern, the number of iterations for texture and depth image compression can be decreased. For example, it can be observed in Figure 7.3 that the 3 × 3 orthogonal pattern of the dark R-D points enable the re-use of depth and texture images, so that only six compression iterations are required. Following this in the second step, by using the pre-defined grid, only four compression iterations of depth and texture images are necessary to obtain again nine R-D points (shown as dark grey in Figure 7.3). In contrast to this, a less-structured search such as a descent method, would require a much larger number of image-compression operation points.

The previous considerations rely considerably on the assumption that the rate-distortion surface model shows reasonable smooth monotonic behavior. This behavior is plausible because it combines two smooth monotonic R-D curves from the individual signals. This is typically achieved with properly designed coding and rendering sub-systems. Only poorly designed systems would show a less smooth, noisy behavior. Having said this, the use of a fast algorithm is even an advantage compared to a descent method because it comes faster to a similar result. The hierarchical search algorithm is summarized in Algorithm 6.

Figure 7.3 Hierarchical search pattern of the involved quantization settings.

Algorithm 6 Hierarchical R-D search - algorithm summary
  Step 1: compress the depth and texture images and render views to generate the R-D points of the search pattern shown by Figure 7.3.
  Step 2: select the R-D point that yields the lowest distortion and satisfies the constraint Rt(qtopt) + Rd(qdopt) ≤Rmax.
  Step 3: initialize a new, finer search pattern with halved step size around the previously selected R-D point.
  Step 4: go to Step 1 if the finest step size is not yet reached.