自动机理论是计算机科学的基础理论之一,其应用领域非常广泛。本文给出一种用加权有限状态自动机(WFA)对灰度图像进行压缩的方法。与传统的图像编码算法相比较,该方法具有压缩比例高、压缩效果较好的优点。首先,介绍课题研究的背景、目的和意义,以及国内外的研究现状并介绍论文中会涉及到的相关知识,如线性空间、正则语言、有限状态自动机等。其次,在给出用字母表Σ={0 ,1,2,3}上的语言表示图像像素地址之后,给出黑白图像的有限状态自动机的表示方法,并通过实例说明了该方法在多分辨率黑白图像上的应用,同时,给出黑白图像的有限状态自动机表示的算法。最后,介绍用加权有限状态自动机(WFA)进行灰度图像的压缩。一幅输入的灰度图像,可以被表示成一个加权有限状态自动机。文中给出两种压缩算法,推导算法和递归推导算法,由推导算法导出的WFA具有较少的状态数,但可能有较多的边;由递归推导算法导出的WFA也许状态数不是最少的,但转移矩阵是稀疏的。本文的创新之处在于:在多分辨率灰度图像的平均存储的概念中引入常数c,得到广义平均存储的概念。平均存储是广义平均存储的特殊情况( c =1时即为平均存储)。当0 < c <1时,是对原来图像的颜色深度的加深,当c >1时,是对原来图像的颜色深度的退化。