Embodiments are provided for compressing a color index map in video coding applications including screen content images. An embodiment method includes obtaining, at a video codec device, an image block, and generating a color index map comprising a plurality of entries and representing the image block. Each one of the entries is assigned a color index indicating a respective color. The method further includes assigning, in a correct prediction map, a first bit-value for each one of the entries that is predictable by a neighboring entry in the color index map, and a second bit-value for each one of the entries that is unpredictable by any neighboring entry in the color index map. Further, an actual value from the color index map for the each one of the entries that is unpredictable by any neighboring entry is added in a sequence of non-predictable color indices.