Generation of similar images using bag context shape grammars

Abstract

Picture grammars have become relevant in generating similar images, because of the increasing need for applications which require such images. Shape grammars are one form of picture grammars. Most shape grammar systems generate an in finite number of images without considering the similarity between them. This is mainly the result of failure to control the application of their rules during derivation. A shape grammar class is therefore imperative not only to generate similar images but also to control the rules applied during derivation. This research demonstrated new approach to generating an in finite number of images that are similar in a controlled manner with the use of a new shape grammar class, called Bag Context Shape Grammars. Bag Context Shape Grammar is also context free, but the application of a rule is controlled by a special vector of integers called the bag, which changes during a derivation. This research goes on to prove that every puzzle grammar, with permitting features, can be converted to Bag Context Shape Grammars. These were further demonstrated in the conversion process. Additionally, this research considered a set of images and demonstrated how Bag Context Shape Grammars can generate a set of images with fewer variable and rules. Then, the different methods these Bag Context Shape Grammars can generate an in finite number of similar images in a controlled manner were demonstrated. As proof of concept, the theories presented in Bag Context Shape Grammars, are implemented in a prototype software called Bag Context Shape Grammar Interpreter which is used to generate images. Images generated by Bag Context Shape Grammars are examined using a Spatial Colour Distribution Descriptor, a content based image retrieval method, used to mathematically check the similarity of images. Finally, the similar images generated using Bag Context Shape Grammars were implemented into a prototype visual password scheme as distractors. The outcome of this study shows that Bag Context Shape Grammars are suitable for the generation of an infi nite number of similar images. These images can be useful in various application areas where similar images are needed, such as, distractors for visual password schemes