Median cut color quantization algorithm: retrospective

Color quantization, reducing the number of distinct colors in a given image with minimal distortion, is a common image processing operation with many applications in visual computing. Heckbert's <i>median cut</i> algorithm, which dates back to the early 1980s, is generally considered the first true color quantization algorithm. Heckbert's seminal work generated numerous subsequent studies extending his algorithm in various ways. In this retrospective, we present a detailed analysis of the median cut algorithm and demonstrate how it influenced later color quantization, vector quantization, and data clustering algorithms.