Generating similar images using bag context picture grammars

Abstract

Formal language theory was born in the middle of the 20th century as a tool for modeling and investigating syntax of natural languages. It was developed in connection with the handling of programming languages. Bag context grammars are a fairly new grammar class where bag context tree grammars have been defined. Bag context is used to regulate rewriting in tree grammars. In this dissertation we use bag context to regulate rewriting in picture grammars and thus to generate similar pictures. This work is exploratory work since bag context picture grammars have not been defined. We use examples to show how bag context picture grammars can be used to generate pictures. In this work bag context picture grammars are defined and used to generate similar pictures. Pictures generated by random context picture grammars and three of their sub-classes are selected and bag context picture grammars are used to generate the same pictures to those selected. A lemma is defined that is used to convert the class of random context picture grammars and three of their sub-classes into equivalent bag context picture grammars. For each grammar selected, an equivalent bag context picture grammar is created and used to generate several pictures that are similar to each other. Similarity is defined by noting small differences that are seen in pictures that belong to the same gallery. In this work we generate similar pictures with bag context picture grammars and thus make the discovery that bag context gives a certain level of control in terms of rules applied in a grammar.