A fractal-based image processing language: formal modeling

摘要

An image spatial accessing methodology based on a formal language (SCAN) is presented in this paper. SCAN is a special purpose context-free language devoted to describe and generate a wide range of 2-D array accessing algorithms from a short set of simple ones. These algorithms may represent sequential scanning techniques used for image processing, such as generation of image data structures (pyramids, trees), encryption, compression, of images, etc., but at the same time they stand as generic spatial data accessing strategies. The SCAN language provides a method of composition of 2-D accessing patterns. The method is motivated by the principle of recursive decomposition of an image array into hierarchical levels for efficient local and global processing. The words of the SCAN language are simple linear forms which convey information for both type of decomposition to be applied, and the specific accessing patterns to be composed.In this paper, we provide the formal definition of the SCAN language and describe the underlying method for spatial access. Properties of the accessing patterns generated by the language are also investigated, and the underlying mathematical model is discussed. Finally, a scheme for the parallel implementation of the SCAN language is presented.