# An Efficient Palette Generation Method for Color Image Quantization
## 3 The Proposed Method
### Initial Palette Generation  
For the color pixel \(x\) = (\(x_{1}\), \(x_{2}\), \(x_{3}\)) in an image, \(x_{1}\), \(x_{2}\), and \(x_{3}\) are integers between 0 and 255. Figure 2 shows the data distribution of the Airplane image in the RGB color space. The color pixel \(x\) = (\(x_{1}\), \(x_{2}\), \(x_{3}\)) in the Airplane image corresponds to a point (\(x_{1}\), \(x_{2}\), \(x_{3}\)) in Figure 2. The 3D RGB space can be divided into non-overlapping cubes. In this study, each cube size is 16 \(\times\) 16 \(\times\) 16 such that there are 4096 cubes in total. These cubes are identified as Cube(\(i\)), \(i\) = 0, 1,..., 4095. For the initial palette generation, the proposed method only considers the cubes in which the point number contained in them is greater than or equal to \(Thr\). These considered cubes are identified as mCube(\(i\)), \(i\) = 0, 1,..., \(N\)\(-\)1. The point number contained in mCube(\(i\)) and the center of all the points in mCube(\(i\)) are denoted by  
Figure 1: (**a**) The color palette is sorted in ascending order of length, (**b**) the searching order of colors in the palette if the color pixel \(x\) = (125, 65, 130).  
\(\text{init}(i)\) and \(\text{init}(i)\), respectively. For example, the point number contained in mCube(0) is equal to 3. Assume that the locations of these points are (81, 115, 35), (85, 118, 40) and (90, 116, 36). Hence, \(\text{initc}(0)=\frac{(81,115,35)+(85,118,40)+(90,116,36)}{3}=\) (85, 116, 37).  
Figure 3 shows 8 cubes. The 8 cubes contain 0, 1, 15, 1, 0, 16, 1, and 0 points, respectively. Assume that the value of _Thr_ is set to 6. The point numbers contained within Cubes 2 and 5 are greater than or equal to 6. Hence, mCube(0) = Cube(2), mCube(1) = Cube(5), \(N=2\), \(\text{init}(0)=15\), and \(\text{init}(1)=16\). Consequently, \(\text{initc}(0)\) and \(\text{init}(1)\) denote the centers of these points contained in mCube(0) and mCube(1), respectively.  
After the \(N\) colors \(\text{init}(i)\), \(i=0\), 1,..., \(N-1\), are determined, the proposed method selects \(K\) colors from the \(N\) colors to generate the initial palette. The steps of initial palette generation are as follows.  
Step 1: The initial palette is an empty set.  
Selected(\(i\)) = 0, \(i=0\), 1,..., \(N-1\). The value of Selected(\(i\)) is equal to 1 which indicates that the color \(\text{init}(i)\) has been selected and added to the initial palette.  
_Cno_ = 0.  
Step 2: If \(\text{init}(j)==\max\left\{\text{init}(i)\ \mid\ i=0,\,1,\,\ldots,\,N-1\right\}\), then the color \(\text{initc}(j)\) is selected and added to the initial palette.  
Selected(\(j\)) = 1 and \(Cno=Cno+1\).  
Figure 3: The 8 cubes contain 0, 1, 15, 1, 0, 16, 1, and 0 points, respectively.  
Figure 2: Data distribution of the Airplane image in the RGB (Red, Green, Blue) color space.  
Step 3: For the colors initc(\(i\)) with Selected(\(i\)) = 0, compute the square Euclidean distance between the color initc(\(i\)) and each color in the initial palette. The minimum value among these square Euclidean distances is identified as Dist(\(i\)). For the color initc(\(i\)), the value DistN(\(i\)) is computed as follows  
\[\text{DistN}(i)=\text{ Dist}(i)\times(\text{initn}(i))^{0.5}. \tag{6}\]  
If DistN(\(j\)) == max [DistN(\(i\)) | if Selected(\(i\)) = 0, \(i\) = 0, 1,..., \(N\)\(-\)1], then the color initc(\(j\)) is selected and added to the initial palette.  
Selected(\(j\)) = 1 and \(Cno\) = \(Cno\) + 1.  
Step 4: If \(K>Cno\), then go to Step 3. Otherwise go to Step 5.  
Step 5: The initial palette is generated.