A new algorithm that color quantizes video sequences is described. It creates multiple color palettes for a video sequence yet avoids the extreme case of creating a palette for each frame. It exploits the fact that there are many instances during a video sequence where minor color changes occur between consecutive frames. The algorithm calculates elementary statistics for each frame to help ascertain whether or not a new color palette needs to be created. The proposed algorithm performs clustering by grouping the colors of a frame into partitions using a method based on principal components. Prior to clustering, a statistical test determines whether or not the colors in the current frame are significantly different than those of the frame where clustering last occurred. If the algorithm detects a significant difference, it performs a clustering phase to calculate a new color palette. The algorithm skips the clustering phase if a significant difference is not detected. Quantized frames are generated by mapping each color in the original frame to its nearest neighbor in the color palette.