# A Mixed Method with Effective Color Reduction
## 2 Materials and Methods
### Overview of the BS+ATCQ Algorithm
#### 2.1.1 The Binary Splitting Method  
This method builds a binary tree to reduce the colors of an image [27]. A binary tree is a data structure where each node can include a maximum of two children. The leaves of the tree created by the algorithm define the quantized palette and identify the subset of pixels of the original image that are represented by the same color in the quantized image.  
Each node of this tree represents a subset of pixels of the original image and stores the information used to perform the successive operations. The node \(j\) represents the subset of pixels \(C_{j}\). The color of this node is computed as \(color_{j}=m_{j}/N_{j}\), where \(m_{j}\) is the sum of the colors of the pixels in \(C_{j}\) (Equation (1)) and \(N_{j}\) is the number of elements of said set (Equation (2)). In addition, there is a \(3\times 3\) matrix associated with the node, denoted as \(\mathbf{R}_{j}\), which stores the sum of the product of each pixel \(p_{i}\in C_{j}\) and its transpose (Equation (3)).  
\[m_{j}=\sum_{p_{i}\in C_{j}}p_{i} \tag{1}\]  
\[N_{j}=|C_{j}| \tag{2}\]  
\[\mathbf{R}_{j}=\sum_{p_{i}\in C_{j}}p_{i}p_{i}^{T} \tag{3}\]  
These three elements allow the covariance of \(C_{j}\) to be computed using Equation (4).  
\[\mathbf{R}_{j}^{\prime}=\mathbf{R}_{j}-\frac{1}{N_{j}}m_{j}m_{j}^{T} \tag{4}\]  
Algorithm 1 shows the main steps of BS. At the beginning of the operations, the tree only includes the root node, denoted \(C_{1}\), which represents the entire set of pixels of the original image. Once the variables \(\mathbf{R}_{1}\), \(m_{1}\) and \(N_{1}\), which are associated with this node, have been computed, the algorithm applies \(q-1\) iterations to define the \(q\) colors of the quantized palette.  
Each iteration selects a leaf \(j\), splits the set of pixels \(C_{j}\) into two subsets and then creates two children for the node \(j\), which represent each of the two subsets.  
To determine the leaf that will be processed during the current iteration, the eigenvalues of the covariance matrix of the current leaves are considered. Based on this information, the algorithm selects the leaf \(j\) with the largest eigenvalue, denoted \(\lambda_{j}\).  
Once the leaf \(j\) has been selected, the two children of this node are created and denoted as \(jA\) and \(jB\). Then, the set \(C_{j}\) is divided into two subsets, \(C_{jA}\) and \(C_{jB}\), with a plane perpendicular to the direction in which the variation of \(C_{j}\) is the greatest and which passes through the mean point. In this case, such plane is perpendicular to the eigenvector \(E_{j}\) corresponding to the principal eigenvalue \(\lambda_{j}\) of \(\mathbf{R}_{j}^{\prime}\). Therefore, the subsets that are associated with the nodes \(jA\) and \(jB\) are defined as follows: \(C_{jA}=\{p_{i}\in C_{j}:E_{j}^{T}p_{i}\leq E_{j}^{T}color_{j}\}\) and \(C_{jB}=\{p_{i}\in C_{j}:E_{j}^{T}p_{i}>E_{j}^{T}color_{j}\}\).  
To complete the definition of the new nodes, the three values associated with each one are computed. After applying Equations (1)-(3) to calculate the values for node \(jA\), the values for node \(jB\) can be easily calculated using Equations (5)-(7).  
\[m_{jB}=m_{j}-m_{jA} \tag{5}\]  
\[N_{jB}=N_{j}-N_{jA} \tag{6}\]  
\[\mathbf{R}_{jB}=\mathbf{R}_{j}-\mathbf{R}_{jA} \tag{7}\]  
when the iterations conclude, the tree has \(q\) leaves that define the quantized palette. Then, the quantized image is obtained by representing the pixels associated with each leaf using the color of such leaf.  
```
1:Set \(C_{1}=\{p_{1},...,p_{N}\}\)
2:Compute \(m_{1}\), \(N_{1}\) and \(\mathbf{R}_{1}\) by Equations (1)-(3)
3:for\(i=1\) to \(q-1\)do
4: Find the leaf \(j\) with the largest \(\lambda_{j}\)
5: Create the two children of node \(j\)
6: Split the pixels of \(C_{j}\) into subsets \(C_{jA}\) and \(C_{jB}\)
7: Compute \(m_{jA}\), \(N_{jA}\) and \(\mathbf{R}_{jA}\) by Equations (1)-(3)
8: Compute \(m_{jB}\), \(N_{jB}\) and \(\mathbf{R}_{jB}\) by Equations (5)-(7)
9:endfor
```  
**Algorithm 1** BS algorithm.