Optimal Color Palette Formula for GIF Files

Creating an optimal color palette for a GIF file involves color quantization, a process that reduces a 24-bit true-color image containing millions of colors down to a restricted 8-bit palette of at most 256 colors. To achieve the least visual distortion, graphics processors rely on mathematical clustering formulas, most notably the Euclidean color distance metric within algorithms like K-Means clustering and the Median Cut method. This article breaks down the exact mathematical formulas used to evaluate color similarity, partition color spaces, and calculate the final optimal palette for GIF files.

The Problem: 24-Bit to 8-Bit Reduction

A standard digital image uses 24-bit RGB color, supporting up to \(16,777,216\) individual colors (\(256 \times 256 \times 256\)). The GIF specification restricts an image frame to an indexed palette of no more than \(256\) colors (\(2^8\)). The goal of color quantization is to find a set of 256 representative color points (\(C = \{c_1, c_2, \dots, c_{256}\}\)) in three-dimensional RGB space that minimizes the total perceived difference between the original pixels and their palette approximations.

The Core Metric: Euclidean Color Distance

To determine which palette color best represents an original pixel, algorithms calculate distance in a 3D coordinate space where axes represent Red, Green, and Blue channels. The fundamental formula used is the standard three-dimensional Euclidean distance:

\[d(P_1, P_2) = \sqrt{(R_2 - R_1)^2 + (G_2 - G_1)^2 + (B_2 - B_1)^2}\]

Because the human eye is more sensitive to green than red, and least sensitive to blue, modern encoders often use a perceptually weighted Euclidean formula:

\[d_w(P_1, P_2) = \sqrt{w_r(R_2 - R_1)^2 + w_g(G_2 - G_1)^2 + w_b(B_2 - B_1)^2}\]

Standard weights often align closely with luminance coefficients: \(w_r = 0.299\), \(w_g = 0.587\), and \(w_b = 0.114\).

The Median Cut Algorithm

The most widespread algorithmic approach for GIF palette generation is the Median Cut algorithm, developed by Paul Heckbert in 1982.

1. Bounding Box Calculation: All pixels from the source frame are plotted in 3D RGB space. The algorithm identifies the minimum and maximum values for each color component to define an enclosing box.
2. Dimension Sorting: It computes the range for each channel: \[\Delta R = R_{max} - R_{min}, \quad \Delta G = G_{max} - G_{min}, \quad \Delta B = B_{max} - B_{min}\]
3. Median Partitioning: The box is sorted along the color channel with the largest range, and pixels are divided into two equal groups at the median index: \[\text{Median Index} = \left\lfloor \frac{N}{2} \right\rfloor\]
4. Iteration: This division repeats recursively until \(256\) distinct sub-boxes are formed.
5. Centroid Averaging: For each of the 256 boxes containing \(k\) pixels, the final palette color \(C_j\) is determined by the mathematical mean of all pixels within that box: \[R_{avg} = \frac{1}{k}\sum_{i=1}^{k} R_i, \quad G_{avg} = \frac{1}{k}\sum_{i=1}^{k} G_i, \quad B_{avg} = \frac{1}{k}\sum_{i=1}^{k} B_i\]

Optimization with K-Means (Minimizing Mean Squared Error)

To refine the palette beyond the initial Median Cut, encoders often apply K-Means clustering to minimize the Mean Squared Error (MSE). The objective function is defined as:

\[J = \sum_{j=1}^{256} \sum_{x \in S_j} \| x - \mu_j \|^2\]

Where:

• \(S_j\) is the set of all pixels mapped to palette color \(j\).
• \(x\) is the 3D RGB coordinate vector of an individual pixel \((R, G, B)\).
• \(\mu_j\) is the mean centroid vector of the palette cluster \(j\).
• \(\| x - \mu_j \|\) is the Euclidean norm.

The algorithm iteratively reassigns each pixel to its nearest centroid using the Euclidean formula, then recalculates each centroid \(\mu_j\) until the objective function \(J\) converges to an optimal minimum. The resulting 256 centroids become the global or local color table stored directly in the GIF data stream.