# Tightly-Coupled Data Compression for Efficient Face Alignment
## 3 Tightly-Coupled Data Compression Algorithm
### K-Means Based Data Quantization with Probability Density-Aware Initialization  
The basic idea of our proposed data compression algorithm is to quantize all the elements of \(\mathbf{A}_{d}\) into \(Q\) predefined values so that each element can be represented with fewer bits. The optimal \(Q\) predefined values can be calculated through minimizing the following equation:  
\[E=\sum\limits_{k=1}^{Q}\sum\limits_{i=1}^{T}1(\mathbf{A}_{d}(i)\in C_{k})\cdot \|\mathbf{A}_{d}(i)-q_{k}\|_{2}^{2} \tag{6}\]  
where \(1(\cdot)\) is the characteristic function, \(T\) is the number of elements in \(\mathbf{A}_{d}\), \(\mathbf{A}_{d}(i)\) is the \(i\)th element in \(\mathbf{A}_{d}\), \(\mathbf{C}=\{C_{1}\), \(C_{2}\),..., \(C_{Q}\}\) divides the data of \(\mathbf{A}_{d}\) into \(Q\) disjoint clusters, and \(q_{k}\) is the representative scalar of cluster \(k\). Solving the minimization problem of Equation (6) is NP-hard [40]. The K-means algorithm [41] can be applied to get the approximate solution. The performance of K-means algorithm heavily depends on the initialization. As shown in Figure 4, the data distribution of \(\mathbf{A}_{d}\) shows single peak characteristics. Traditional random initialization for the K-means algorithm cannot capture the characteristics of the data distribution of \(\mathbf{A}_{d}\), so that the acquired result is far from optimal. A probability density-aware initialization method, which is to say the initial quantization step size (cluster size) is inversely proportional to the probability density distribution of the data in order to fully capture the data distribution of \(\mathbf{A}_{d}\), is proposed in this paper. Thus, we have  
\[\int_{v_{k-1}}^{v_{k}}p(x)dx=const.=\tfrac{1}{Q}\quad(k=1\cdots Q) \tag{7}\]  
where \(v_{k-1}\) and \(v_{k}\) are lower and upper bounds of the \(k\)th quantization step respectively. So the optimal initialization strategy can be estimated through the following equation:  
\[\begin{array}{c}\underset{v_{1}\cdots v_{Q-1}}{\min}\sum\limits_{k=1}^{Q} \left\|\int_{v_{k-1}}^{v_{k}}p(x)dx-\tfrac{1}{Q}\right\|^{2}\\ s.t.\quad \begin{array}{c}v_{0}=V_{\min}\\ v_{Q}=V_{\max}\end{array}  \tag{8}\]  
where \(V_{\min}\) and \(V_{\max}\) are minimum and maximum values of \(\mathbf{A}_{d}\) as shown in Table 1. Unfortunately, the exact solution of the above equation is difficult. In this paper, an approximate solution to the above problem is proposed as follows since only reasonable initializations for the K-means algorithm are needed. All the elements in \(\mathbf{A}_{d}\) are sorted in ascending order and stored in an array SA. The lowest and highest quantization step bounds can be calculated with the following equation:  
\[v_{0}=\text{SA}(1),v_{Q}=\text{SA}(T) \tag{9}\]  
Figure 4: Typical example of the estimated probability density function (PDF) for the elements in \(\mathbf{A}_{1}\). The remaining quantization step bounds are calculated with Equations (10) and (11) as follows:  
\[idx=\left\lfloor\frac{k\cdot T}{Q}\right\rfloor \tag{10}\]  
\[v_{k}=\text{SA}(idx)\ (k=1\ldots\ Q-1) \tag{11}\]  
where \(\lfloor\bullet\rfloor\) is the floor function that rounds the element to the nearest integer towards minus infinity. With the above algorithm, the number of elements between consecutive quantization steps bounds is nearly the same, so that Equation (8) is approximately solved. The most important thing is that all the quantization steps bounds can be efficiently estimated with the above algorithm. However, we do not choose the mid-value between the lower and upper bounds as initial values for the K-means algorithm since the data distribution inside the quantized region is not uniform. Instead, the initial value for the K-means algorithm is set as the mean value of all the elements that fall in the same quantized region as follows. First, the set of all the elements that belong to the \(k\)th quantization step is calculated.