Many image display devices limit the colors which can be simultaneously displayed to a small set of colors called a color palette. Usually, each element of the color palette can be selected by the user from a wide variety of available colors. Such device restrictions make it particularly difficult to display natural color images since these images usually contain a wide range of colors. The color quantization problem can be considered in two parts: the selection of an optimal color palette and the optimal mapping of each pixel of the image to a color from the palette. This paper applies a hierarchical tree structure to the design of the color palette. The tree structure allows palette colors to be properly allocated to areas of the color space which are densely populated and, in addition, greatly reduces the computational requirements of the palette design and pixel mapping tasks. Methods are presented for incorporating performance measures which reflect subjective evaluations of image quality. Incorporation of these measures into the quantization problem results in significantly improved image quality. The algorithms presented in the paper produce high quality displayed images with minimum artifacts and require far less computation than previously proposed algorithms using unstructured color palettes.