Overlapped Rectangle-Based Image Representation And Relevant Operation Method

Based on Non-symmetry Anti-packing pattern representation Model (NAM), a compact and lossless multi-valued image representation method, i.e. Overlapped Rectangle-Based Image Representation method (ORBIR), is presented to support fast image operations. ORBIR overcomes some defects in hierarchical data structures and uses rectangles, which are allowed to be overlapped in space, to represent multi-valued images. As a result, ORBIR significantly reduces the space required to store an image. While obtaining high compactness, ORBIR is capable of supporting fast image operations.Because all rectangles used to represent an image are stored in a sequential list for saving storage space, ORBIR has introduced an unwanted side-effect, i.e., losing the explicit space relationship among the rectangles, which makes some image operations hard to be implemented. In order to restore the explicit space relationship from the ORBIR, a data structure, referred to as Longitude and Latitude Grid (L2G), is presented. With the help of L2G,neighbor-finding process can be executed fast in ORBIR.Geometric properties, such as perimeter and connected component, have been widely used in image segmentation and pattern recognition. Assisted by the ORBIR-based algorithm for neighbor-finding, an abstract algorithm framework, which can be used to compute geometric properties of images represented by ORBIR, is presented. After analyzing the nature of perimeter computation and connected component labeling, two algorithms, which compute perimeter and label connected component respectively, are embodied from the abstract algorithm.Moments have been broadly used in engineering. On the basis of the investigation of different moments, the concept of generalized moments is firstly defined and then, an abstract algorithm framework for computing the accurate generalized moments is presented. The framework replaces integrals on 2-dimensions space by summations on 1-dimension ORBIR list without introducing the error incurred by discrete sampling, and therefore, reduces the computation complexity for moments generation. In order to verify the effect of this framework, two algorithms, one for geometric moments generation and one for Legendre moments generation, are presented.Some experiments are performed to verify the compactness and convenience of ORBIR. On the aspect of the compactness, for binary images and multi-values images, the average ratios of the number of linear quadtree nodes to the number of ORBIR rectangles are 4.46 and 1.66 respectively, and the average ratios of the number of bits required by linear quadtree to the number of bits required by ORBIR are also 4.46 and 1.66 respectively. According to these results, it can be concluded that ORBIR is more compact than linear quadtree. On the aspect of the convenience, the average ratios of CPU elapsed time of linear quadtree-based neighbor-finding algorithm and for quadtree-based neighbor-finding algorithm to CPU elapsed time of ORBIR-based neighbor-finding algorithm are 4.98 and 20.88 respectively. The average ratios of CPU elapsed time of linear quadtree-based perimeter computation algorithm and for linear quadtree-based connected component labeling algorithm to CPU elapsed time of the corresponding ORBIR-based algorithms are 10.30 and 5.50 respectively. For binary images and multi-valued images, the average ratios of CPU elapsed time of Delta algorithm, which is the fastest algorithm for geometric moments generation, to CPU elapsed time of the ORBIR-based algorithm are 80.81 and 1.76 respectively. For binary images and multi-valued images, the average ratios of CPU elapsed time of Yap's algorithm, which is the fastest algorithm for accurate Legendre moments generation, to CPU elapsed time of the ORBIR-based algorithm are 83.61 and 1.62 respectively. All these results reveal that the ORBIR-based algorithms are much faster than the contrastive algorithms.From the theoretical analysis and the experimental results, it can be safely concluded that, while obtaining high compactness, ORBIR is capable of supporting fast image operations.