3.15. The Original Diversity Algorithm   

The algorithm works as follows:


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.