3.15. The Original Diversity Algorithm   

The algorithm works as follows:

• Run a histogram on the entire picture to determine `pixel counts' for each desired colour in the colourmap. Note that any colours with a pixel count of 0 should be discarded. These colours will obviously never be used and would waste valuable colourcells.
• Pick the colour with the highest pixel count. This is the `overall' colour of the picture.
• Run through the list of un-picked colours and find one with the greatest `distance' from the first colour. This is the colour that is most diverse from the `overall' colour. Distance is defined by the traditional `Euclidian' formula:
   
  
  
  where r1, g1 and b1 are the RGB components of one colour and r2, g2 and b2 are the RGB components of another colour. d is the distance between the two colours.
• For each colour remaining in the `unpicked list', compute the distance from it to each of the colours in the `picked' list. Find the colour in the unpicked list that is furthest from all of the colours in the picked list. Pick this colour. Repeat until all colours have been picked.

3.15.1. The Modified Diversity Algorithm   

Tom Lane of the Independent JPEG Group came up with a couple of improvements to the Diversity Algorithm, resulting in the Modified Diversity Algorithm, which XV currently uses. He rightly pointed out that, on displays with an intermediate number of colours (~64), too much emphasis was being placed on getting `different' colours and not enough emphasis on getting the `correct' colours.

His idea was to modify the sorting criteria slightly, to better balance the allocation between diverse colours and `popular' colours (colours with high pixel counts). His solution to the problem was to alternate between picking colours based on diversity and based on popularity.

In the modified Diversity Algorithm, as implemented in XV, the first colour picked is the most popular colour. The second colour picked is the colour furthest away from the first colour. The third through tenth colours picked are all picked using the normal Diversity Algorithm. The eleventh colour picked is based on popularity, (the un-picked colour with the highest `pixel- count' is chosen). The twelfth colour is once again picked on diversity. The thirteenth colour is chosen on popularity, and so on, alternating, until all the colours have been picked.

The other major modification was that the `diverse' colours are picked in O(n^2) time instead of O(n^3) time.