3.14. XV's Diversity Algorithm 3.14. XV's Diversity Algorithm By John Bradley
The first step of this colour allocation algorithm is to sort the colours in order of decreasing `importance'. The colours are then allocated in this order, so that if the colour allocation fails after m colours, then at least it was the m most important colours that were allocated.
There are many different criteria that one could use to define which colours in an image are `important'.
We could just ignore the problem and take the first m colours from the colourmap. This would, however, be clearly unacceptable. The entries in a colourmap are generally not sorted in any order whatsoever. Even when the colours are sorted in some order, it's not likely that it will be a useful order. For example, in a greyscale picture, the greys may be ordered from black down to white. If we were to assume that this was a `useful order', and we could only get the first few colours, we would end up with all very black colours and no whites or middle greys.
Thus, we need to determine a colour's importance to the overall picture quality.
A colour's `importance' can be determined intuitively by asking the question "If we can only use on of these two colours, which one would make the picture look better?". The aim is to have the picture be recognisable with very few colours. Additional colours should smooth out colour gradation, but should not add any significant detail, nor change the colour balance of the overall picture.
Picking colours in this order is not a trivial task, and is open to some degree of subjectivity. One method might involve calculating a histogram of the data to find out which colours are used the most often (i.e., which colours have the greatest number of pixels associated with them), and using those colours first. This approach is certainly valid, but places too much emphasis on large, uniformly coloured regions, such as backgrounds. This is not generally where the `interesting' portion of the picture is found.
For example, suppose a picture consists of a blue background (consisting of light, medium and dark shades of blue) with a small red square on it. If we were to choose two colours by order of decreasing usage, light and medium blue may be chosen. But this would result in us not seeing the red square! (The red would be approximated by the closest blue). Clearly, we should use the red and one of the blues. But which blue? It could be argued that since there are three blues and only one of them can be used, medium blue sould be selected, since it is the `average' blue, This is where it becomes somewhat subjective. The diversity algorithm would pick light blue, since it is most frequently used.
Thus, this algorithm tries to maximise the diversity of the colours. By picking colours that are as unlike each other as possible, the `inhabited' portion of the RGB colourspace is covered as quickly as possible.
Generally, this tends to bring out the major details (such as objects) in the picture first, since the details are likely to involve contrasting colours. As more colours are picked, gaps in the RGB space are filled. This smoothes out the colour gradations and brings out lesser detail (such as texture).
