# Latitude-Adaptive Integer Bit Allocation for Quantization of Omnidirectional Images
## 5 Algorithm  
### Two-Step NNI Bit Allocation  
It is desirable to implement a solution with an NNI number of bits for each quantizer. However, the problem (5) is a combinatorial optimization problem, and the derived \(b_{k,l}\) in Section 4 does not guarantee the allocation of NNI bits. The greedy algorithm is a heuristic algorithm commonly used to find approximate solutions to combinatorial optimization problems, with lower complexity compared to exhaustive search. Compared with methods like genetic algorithms and simulated annealing algorithms, the greedy algorithm is relativelysimple to design and implement. Allocating integer bits to a large number of quantizers directly is challenging. Hence, we propose a two-step algorithm to find an NNIBA. Referring back to Figure 2, our bit allocation method is executed in two steps. First, we consider allocating bits to blocks at different latitudes according to (10) and then proceed to allocate bits to each quantizer within each block, as illustrated in Figure 2e,f, respectively. The impact of blocks at different latitudes on WMSE varies, justifying the allocation of different numbers of bits. Since \(\omega_{k}\) increases when getting close to the equator, intuitively, we allocate more bits to blocks near the equatorial region to account for this difference. As discussed in Theorem 1, we can replace the WMSE distortion of all quantizers within a block with the average distortion \(D_{k}(b_{k})=g_{k}2^{-2\frac{b_{k}}{L^{2}}}\), and the overall distortion \(D\) is denoted as \(D=2K\sum_{k=1}^{K}D_{k}\). Notice that \(g_{k}\) is related to the normalized pdf and variance of the coefficients at latitude \(k\), necessitating the calculation of their empirical distribution, as seen in Figure 2d. Based on Corollary 1, our approach involves a progressive allocation of bits to the neediest quantizer, meaning the one that incurs the highest distortion with the current bit assignment. This iterative process continues one bit at a time until all available bits are allocated, as detailed in Algorithm 1. ```
0:\(B\), \(g_{k}\), \(K\)
1: Initialize the bit allocation to zero, so that \(b_{k}^{0}=0\) for each \(k=1,\ldots,K\) and \(m=0\). Set \(s_{k}^{0}=D_{k}(0)\). 2:while\(m<\frac{B}{2K}\)do
3: Find the index \(j\) with the maximum \(s_{k}^{m}\). 4: Set \(b_{j}^{m+1}=b_{j}^{m}+1\). 5: Set \(b_{k}^{m+1}=b_{k}^{m}\) for each \(k\
eq j\). 6: Set \(s_{k}^{m+1}=D_{k}(b_{k}^{m+1})\). 7: Increment \(m\) by \(1\). 8:endwhile
9:return\(b_{k}\) for \(k=1,\ldots,K\). ```  
**Algorithm 1** Tile bit allocation  
After we allocate NNI bits to each tile, the subsequent step involves the allocation of \(b_{k}\) bits within one block of size \(L\times L\) at latitude \(k\), as depicted in Figure 2f. Remark 1 provides the theoretical justification for such an allocation, which states that we allocate bits to the quantizer generating the maximum distortion in a block. The allocation process follows a similar methodology as before. The budget of one block with latitude \(k\) is \(b_{k}\), and the distortion of the \(l\)-th quantizer is \(d_{l}(b_{k,l})=h_{k,l}\sigma_{k,l}^{2}2^{-2h_{k,l}}\). In light of these considerations, we derive Algorithm 2. The output of Algorithm 2 represents the NNIBA for \(b_{k,l}\) at latitude \(k\). By repeating Algorithm 2\(K\) times, we successfully complete the process of assigning bits to each scalar quantizer. Our bit allocation methodology is versatile, applicable to the design of quantizers, as well as the enhancement of other quantization approaches. We compare the time complexity between our two-stage greedy method and the method of directly applying the greedy algorithm to all quantizers. As described in the optimization problem (5), we need to allocate \(\frac{B}{2K}\) bits to \(KL^{2}\) scalar quantizers. First, we consider the complexity of applying the greedy algorithm directly to \(KL^{2}\) quantizers. In each round of bit allocation, we need to determine the maximum distortion among \(KL^{2}\) quantizers.