Savchynskyy B. Context-free grammar constructions for recognition of textual and graphical document images

The following particular results have been achieved: the structure of grammatical rules has been extended, namely, such rules are introduced, which allow image fragments to intersect. It is demonstrated that after such obviously expedient extension the task of real image parsing remains still effectively solvable. It is proved that for a certain class of similarity functions such extension does not violate their additivity, which is a necessary condition of an effective parsing. Namely, similarity of a complex image is determined by a total similarity of its constituents, even if they intersect. For the investigated class of two-dimensional grammar constructions an image derivation procedure was build, which consists in reviewing already derived image fragments and creating the new ones according to derivation rules. This procedure has a polynomial complexity, however its space complexity depends on an order of image fragments review. The task of optimal review ordering to minimize space complexity wasformulated and solved. A subclass of two-dimensional context-free grammar constructions was defined, which has a linear parsing complexity with respect to an image size. This complexity is much less then the corresponding one in a general case of context-free constructions. Constructions of this subclass can be considered as a two-dimensional generalization of regular grammars. The main principles of fast software creation for image recognition on a base of two-dimensional context-free constructions have been formulated.