IMAGE-CODING USING FINITE-STATE AUTOMATA

Image coding using quadtrees is useful in many applications and is wel l known in computer vision and graphics. We draw a parallel between qu adtrees and rational languages that are recognizable by finite state a utomata (FSA), also known as automata. The FSA are shown to be an inte resting alternative to the corresponding quadtrees. Binary image (0=bl ack, 1=white) coding using a FSA follows these two steps: (1) automato n construction based on the image quadtree, (2) automaton minimization . The display of the coded image is simply obtained by stepping throug h the automaton. We demonstrate how simple image operations can be eff iciently implemented directly with FSA. Examples are also presented to illustrate the relationship between the FSA complexity and the coded images. Finally, the generalization of this approach to gray-level ima ges, color images, and volume data is discussed. We believe that this automaton coding approach will be useful in developing efficient image and data compression algorithms.