Colour has proved to be a very powerful feature for image indexing. There are many examples of image retrieval systems based on colour or chromaticity histograms in the literature, following on from the histogram intersection method of Swain and Ballard. Here we propose a compact representation of the chromaticity histogram that achieves very good performance in image retrieval. Specifically, we use a new type of polynomial interpolation in two variables, which relies on the Padua points as interpolation nodes. What we obtain is a vector of coefficients, that represents the interpolation polynomial and is “characteristic” for an image, and that can be compared to the corresponding vectors of other images. Experiments show that our new compact Padua point representation supports excellent indexing and recognition.