A novel gray image representation using overlapping rectangular NAM and extended shading approach

In this paper, inspired by the idea of overlapping rectangular region coding of binary images, we extend the SDS design, which is based on overlapping representation from binary images to gray images based on the non-symmetry and anti-packing model (NAM). A novel gray image representation is proposed by using the overlapping rectangular NAM (RNAM) and the extended Gouraud shading approach, which is called ORNAM representation. Also, we present an ORNAM representation algorithm of gray images. The encoding and the decoding of the proposed algorithm can be performed in O(n log n) time and O(n) time, respectively, where n denotes the number of pixels in a gray image. The wrong decoding problem of the hybrid matrix R for the overlapping RNAM representation of gray images is solved by using the horizontal, vertical, and isolated matrices, i.e., H, V and I, respectively, which are used to identify the vertex types. Also, we put forward four criteria of anti-packing homogeneous blocks. In addition, by redefining a codeword set for the three vertices symbols, we also propose a new coordinate data compression procedure for coding the coordinates of all non-zone elements in the three matrices H, V and I. By taking some idiomatic standard gray images in the field of image processing as typical test objects, and by comparing our proposed ORNAM representation with the conventional S-Tree Coding (STC) representation, the experimental results in this paper show that the former has higher compression ratio and less number of homogeneous blocks than the latter whereas maintaining a satisfactory image quality, and therefore it is a better method to represent gray images.