An improved technique for compressing a color or gray scale pixel map representing a document using an MRC format including a method of segmenting an original pixel map into two planes, and then compressing the data or each plane in an efficient manner. The image is segmented such that pixels that compress well under a lossy compression technique are placed on one plane and pixels that must be compressed losslessly are placed on another plane. Lossy compression is then applied to the lossy pixel plane while lossless compression is applied to the lossless pixel plane.