The initial idea of the popularity algorithm is to build the colormap by finding the K most frequently appearing colors in the original image.
Therefore the colors are stored in a histogram. The K most frequently occuring colors are extracted and they are made the entries in the color table. Now the true image can be quantized.
Popularity algorithms are another form of uniform quantization. However, instead of dividing the color space into 256 regions these algorithms break the color space into much smaller, and consequently many more, regions. One possible implementation is to divide the space into regions 4x4x4 in size (262,144 regions). The original colors are again mapped to the region they fall in. The representative color for each region is the average of the colors mapped to it. The color map is selected by taking the representative colors of the 256 most popular regions (the regions that had the most colors mapped to them). If a non-empty region is not selected for the color map its index into the color map (the index that will be assigned to colors that map to that region) is then the entry in the color map that is closest (Euclidean distance) to its representative color).
- Create a block or box surrounding the points; it should be just large enough to contain them all.
- While the number of blocks is less than the desired palette size:
- Find the block with the longest side out of all blocks.
- Cut this block into two blocks along its longest side. Cut it in such a way that half of the points inside the block fall into each of the two new blocks (that is, we split it through the median, thus the name).
- Shrink these two new boxes so that they just barely contain their points.
- Average the points in each box to obtain the final set of palette colors.