Binary image compression using efficient partitioning into rectangular regions

A new binary image coding technique is presented. In the new technique, the black regions in the input image are first partitioned into a number of nonoverlapping rectangles. The partitioning can be achieved using one of two different algorithms. The first algorithm can partition the input image into the minimum number of nonoverlapping rectangles at the expense of complex implementation. The second algorithm gives a near optimal partitioning with very simple implementation. After the black regions of the input image are partitioned into rectangles, the coordinates of two opposite vertices of each rectangle are compressed using a simple procedure that allows the decoder to reconstruct the original image. Test images of different types, sizes, and complexities are used to demonstrate the improvement of the new technique over the other currently available binary image compression techniques. >