Study On The Storage And Operation Method Of Rectangle NAM Image Representation Model

With the image representation based on Non-symmetry Anti-packing pattern representation Model(NAM), a rectangle NAM Image representation is presented, which searched start point based on raster order, matched rectangle according maximum area and decomposed image non-overlapping. Its coding and decoding algorithms are presented and analyzed, then the storage structure of direct storage method is given and data amount is analyzed, finally improvement idea of direct storage method is presented.Single value storage method of binary rectangle NAM image representation can reduce data amount by reducing the number of sub-pattern instance and not saving the v field of sub-pattern instance. Full value storage method reduce data amount by not saving the x, y fields of sub-pattern instance. The compression ratios of Single value storage method and full value storage method are both near 2 times of that of direct storage method.Limited rectangle storage method decreased the bits of the w, h fields by limiting the rectangle size of sub-pattern instance of full value storage method. The limited rectangle storage method need choose appropriate maximum rectangle according the complexity of the image.Classified storage method classified sub-pattern instances by their size, then saving the w, h fields with different bits when the class is different. Less sub-pattern instance needed fewer bits. With experimental data, the compression ratio of classified storage method is bigger than that of single value storage.Huffman code of sub-pattern instance can improve compression ratio by reducing the relativity of sub-pattern instance. Its coding unit is the sub-pattern instance. For unifying and decreasing the coding unit, a standard sub-pattern instance storage method is presented. Any rectangle can compounded by a base rectangle and base operations less then three. The base rectangles and operations are new coding unit. For not saving Huffman coding tree, a storage method based on predefined code is presented and a predefined code table is given. With experimental data, the compression ratios of Huffman code of sub-pattern instance, Huffman code of standard sub-pattern instance and predefined code storage method are all much bigger than that of full value storage method.Gray scale NAM image representation has two representations, direct representation and bit plane decompose representation. The direct represented gray scale NAM image can improve compression ratio by full value storage, limited rectangle storage and Huffman code storage. The bit plane decompose represented gray scale NAM image can use the storage method of binary NAM image directly. Aim at the shortage of bit plane decompose based on binary code, a new bit plane decompose base on Gray code is presented. The complexity of bit plane based on Gray code is less than that based on binary code, so its compression ratio is higher than that based on binary code.With the experimental data, the compression ratio of improved binary NAM image is 5.45 to 9.70 times of that of quadtree, 2.16 to 5.09 times of that of run length code, 1.42 to 2.82 times of that of CCITT G3, and 0.55 to 0.87 times of that of CCITT G4. The compression ratio of improved gray scale NAM image is 1.01 to 1.72 times of that of run length code, 0.95 to 1.18 times of that of GIF image format. As discussed above, the improved storage method of rectangle NAM image is a high performance storage method. It can be used for lossless compression of binary and gray scale image.The formatted method of rectangle NAM image representation reconstructed the ubiety of sub-pattern instance with five queues. It made connectivity operation between sub-pattern instances easier. With the class of connectivity between sub-pattern instances, the based operations of connectivity such as verdict, search and ergod are researched. The complexity of connectivity search at the worst situation is O(logN), N is the side length of image. The complexity of connectivity ergod is O(N_q), N_q is the number of sub-pattern instances.With the connectivity operation of sub-pattern instance, contour extraction, Euler number computing and connected component labeling of binary rectangle NAM image are researched. With the experimental data, operation time of contour extraction of binary image represented by rectangle NAM is 0.31 to 0.86 times of that of image represented by matrix, operation time of Euler number computing of binary rectangle NAM image is 0.11 to 0.63 times of that of the pattern algorithm, operation time of connected component labeling of binary image represented by rectangle NAM is 0.08 to 0.37 times of that of image represented by matrix, 0.05 to 0.12 times of that of image represented by quadtree. Either from theoretical or from experiment, the formatted storage of rectangle NAM image is good at image operation.