Image coding using finite state automata
Charles E. Quenneville, Jean Meunier · Optical Engineering · 1996
Image coding using quadtrees is useful in many applications and is well known in computer vision and graphics. We draw a parallel between quadtrees and rational languages that are recognizable by finite state automata (FSA), also known as automata. The FSA are shown to be an interesting alternative to the corresponding quadtrees. Binary image (0=black, 1=white) coding using a FSA follows these two steps: (1) automaton construction based on the image quadtree, (2) automaton minimization. The display of the coded image is simply obtained by stepping through the automaton. We demonstrate how simple image operations can be efficiently 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 images, 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.