The Similarity of Images Generated by Bag Context Shape Grammars

Shape grammars are a class of grammar in formal language that uses spatial rules to generate images. Shape grammars generate images in a way that is not always regulated. That is, they generate images without considering the similarity between them. This is largely because they are context free. As such, the application of a rule is not controlled during derivation. Bag Context Shape Grammars (BCSGs), a class of shape grammars that uses context to control the application of context free rules during derivation, was used to generate images in a regulated manner. In this paper, we examine the similarity of the images generated by BCSGs. The Spatial Colour Distribution Descriptor (SpCD), a content based image retrieval was used to mathematically check the similarity of the bag context shape grammar generated images. The outcome of this study shows that BCSGs are good for the generation of images that are similar. This type of approach can be useful in the generation of distractor (similar) images for visual password systems and others.

I. Introduction

Image generation, a key subject in computer science and mathematics, has been applied to various fields, such as medicine, document processing, generating of clothing, as well as in video games [1], [2]. Due to the relevance of image generation in computer science, new methods of syntactically generating images have emerged in the past few years. The use of formal grammars, in generating syntactic or abstract images, is one example of the new methods of image generation [3]. A formal grammar is an abstract structure with which one can generate a set of images [4]. There are many image generating grammars that exist and more are still being developed. One such grammar is the shape grammars. A shape grammar uses spatial rules to generate images [5], [6].