The non-symmetry anti-packing image representation (NAIR) uses a sequence of the instances of some predefined prototypes to represent an image. While significantly reducing the instances required to represent an image in contrary to the quadtree and the linear quadtree, however, NAIR has lost the explicit space relationship among these instances and hence made some geometric operations such as perimeter computation hard to be implemented. In this paper, longitude and latitude grid (L2G), a data structure which can restore lost space relationship from the NAIR is first presented, and then a novel algorithm to compute the perimeters of the images represented by the NAIR is presented. The experimental results show that the new algorithm has saved at least 90% of the running time comparing with that based on the quadtree.