With the increase in the resolution of images, arises the need to compress these images effectively without much loss, for easy storage and transmission. Sparse matrices are matrices that have majority of their elements as zeroes, which brings in the possibility of storing just the non-zero elements in a space efficient manner using various formats. Images, which are essentially matrices, if somehow expressed as sparse matrices, can be similarly stored. The rectangular segmentation is a method that can be used to do so. In this paper, we analyze the space complexity of various storage formats for benchmark matrices and the suitability of these formats to compress images using rectangular segmentation method. © 2014 IEEE.