3.12. The Popularity Algorithm   

By Tom Boyle and Andy Lippman (MIT's Architecture Machine Group) and Ephraim Cohen (New York Institute of Technology) from Heckbert (1982)

The assumption of this algorithm is that the colormap can be made by finding the densest regions in the colour distribution of the original image. The popularity algorithm simply chooses the K colours from the histogram with the highest frequencies and uses these for the colourmap. This can be done with a simple selection sort. This will take time O(NK), where N is the number of colours in the histogram.

The popularity algorithm functions well for many images, but performs poorly on ones with a wide range of colours, or when asked to quantise to a small number of colours (say < 50). It often neglects colours in sparse regions of the colour space.