Grayscale Image Compression Method Of Weighted Finite State Automata

Automata theory is one of the foundations of computer science, its application fields are very extensive. In this note an approach is introduced to compress digital grayscale image by using weighted finite automata (WFA). This method has an advantage of higher compression and without further degradation of quality than the classical image coding algorithms.Firstly, the background, the purpose and significance of the research, the situation at home and abroad, and the related knowledge, such as linear space, regular language, finite state automata, etc are introduced.Secondly, the addressing scheme of pixels using language over the alphabetΣ={0 ,1,2,3}is given. Then the method of finite automata representation of bi-level image is also given. Examples to show the applications of the method in multi-resolution bi-level image are list, and the algorithm that using finite automata represent bi-level image is given.Finally, weighted finite automata (WFA) is introduced in order to compress grayscale image. For a grayscale image, the WFA can be constructed to describe the image. In this note two kinds of compression algorithms are given, the inference algorithm and the recursive inference algorithm. The WFA derived by the inference algorithm has less state, but there may be more edges. The number of states of the WFA derived by the recursive inference algorithm may be not the least, but the transition matrices are sparse.The innovation of this note lies in: the constant c is introduced in the concept of the average preserving in the multi-resolution grayscale image, thus the concept of average preserving is generalized. Average preserving is a special case of generalized average preserving (when c =1it is average preserving).When 0 < c <1,it is color depth deeper for original image, and when c >1, it is color depth degradation for original image.