国家863通信主题支持课题 算子T作用于R²的某一子集Q并收敛于称为IFS吸引子的一个唯一的 的子集.可得: G=lim n∞ ω^on(Q) (3) 其中G为吸引子,而ω^On表示映射ω的n次迭代,于是有ω^o0(Q)=Q和ω^o(n+1)(Q)=ω(ω^on(Q)),所以吸引子就是变换的不动点,它等于变换{ω₁,ω₂,…,ω_N}作用于它本身所得的N个部分的拼贴组合.可见,IFS变换的吸引子是测度空间( ,d)上的非空、紧致子集.因此对初值x₀∈ 迭代作用算子T,可得序列(x_n)∈ ,表示如下: x_n+1=T(x_n),n＞0 (4) 若对任意初始值x₀∈ ,序列(x_n)收敛到空间中的同一个点x^*,则x^*为T的吸引子,于是给定T有: x^*=T^x(x), x∈ (5) 若 为一矢量空间,根据式(2)T可写为如下形式: x∈ ,T(x)=Ax+B (6) 其中A为线性算子,B为常数算子.对输入为u_n,输出为y_n,状态为x_n的线性时不变离散系统(如图1所示). 其动力系统方程如下: 状态方程:x_n+1=A_xn+B_un (7) 输出方程:y_n=C_xn+D_un (8) A为状态转移矩阵.若式(7)中的u_n为常数,式(6)与式(7)是一致的,因此可以认为x∈ 是按T变化的系统的状态.为了用IFS分形变换来编码一幅自然图像,图像必须表示成一个紧致、非空集合.根据有限覆盖定理,图像可表示为有限个子图像的并集.然而图像若只是非空紧致集的话,还不能用线性系统理论来进行分析,所幸Jacquin^[7]提出了局部IFS分形编码算法,该算法是基于图像中不同尺度的局部图像之间具有自相似性,这种确定自相似是仿射变换下的线性自相似;这使得用线性系统理论对局部IFS分形变换进行分析就显得十分自然了.将图像看成线性系统的一个状态,初始图像是系统的初始状态,输入为常量,IFS的吸引子可看作系统的稳定状态.这样,可通过研究线性系统的结构来了解IFS分形变换编码的误差特性. 第 1 期 马 波:线性系统理论在分析分形-小波变换编码误差中的应用 电 子 学 报 2000年 3 自子树量化算法SQS的线性系统模型 由于小波基具有与分形编码所要提取的自相似性相同的特性,使得小波变换作为分形块编码的分析工具是非常适宜的.可分离的二维双正交小波基是由一组分离的小波ψ_lh(x,y),ψ_hl(x,y),ψ_hh(x,y)和(x,y)经过伸缩、平移构成的.我们用o来表示Ω={lh,hl,hh}三个方向中的一个,并选择可分离的对称(或反对称)的双正交小波基.2^N×2^N的图像I_mg的离散小波变换可表为基函数的线性组合: W_J={^J_k,l|0k,l＜2^J}∪{ψ^j_o,k,l|o∈Ω;Jj＜N;ok,l＜2^j} (9) 其中,基函数^j_k,l和ψ^j_o,k,l的系数分别为〈 ^j_k,l,I_mg〉和〈 ^j_o,k,l,I_mg〉, ^j_k,l为双尺度函数, ^j_o,k,l为小波.小波分解的一个重要性质就是它们保存了图像特征的空间局部性.尺度函数^J_k,l的系数与图像中坐标(左下角)为(2^jk,2^jl)大小为2^J×2^J的块内像素的平均值成比例,而与该区域相关的小波系数分别在三个子树中,小波子树的根是小波ψ^J_o,k,l的系数,其中o∈Ω,这些系数对应块的粗尺度的信息.树中每个小波系数〈 ^j o,k,l,I_mg〉对应同样空间位置、同方向的四个子系数.这些子系数由下一层更精细尺度上的小波的系数组成,它们是ψ^j+1_o,2k,2l,ψ^j+1_o,2k+1,2l,ψ^j+1_o,2k,2l+1和ψ^j+1_o,2k+1,2l+1.一个小波子树包括根系数以及在三个方向的所有子系数.尺度函数^j_k,l位于与以ψ^J_o,k,l为根的子树相同的区域,把^J_k,l作为与此子树相对应的尺度函数.对图像中的块的小波分解使得空间中一个小区域里的一组像素对应一个小波子树以及与该子树相联的尺度函数系数.定义一个线性 输入子树 算子S^J_k,l;R^22NR^22(N-J)-1,它从一幅图像中提取一个树根中包括了某一个方向的ψ^J_o,k,l的系数的子树,此处只考虑一个方向而不是三个方向.定义了一个线性 输出算子 (S^J_k,l)^*,它在一个全零的图像中插入一个根对应系数为ψ^J_o,k,l,o∈Ω的子树.算子 是由从粗尺度到细尺度的系数变换、乘1/2以及对最细尺度的系数的舍弃等步骤组成的. ^k为截短和重排子树k次. _k为对称变换算子,它对所选定的双正交小波基在每个尺度对小波系数产生作用.于是在小波变换域中,可以得到: S^N-R_ΓI_mg≈g_{Γ P(Γ)} ^D-RS^N-D Π(Γ)I_mg (10) 把用别的子树(域子树)来对某一子树(值子树)进行量化,称为 子树量化, 记为S^N-R_ΓI_mg,其中Π:  表示对每一值子树从域子树集 中选定了一个域子树.对式(10)用小波系数来代替子树可得ψ^j_γ(对和ψ的方向及平移描述,简记为γ)在S^N-R_ΓI_mg中的一组方程: 〈 ^j_γ,I_mg〉≈(g_Γ/2^D-R)〈 ^j-(D-R) γ,I_mg〉=(g_Γ/2^D-R)〈T ^j_γ,I_mg〉 (11) 这里映射T包括块选择、平均、亚采样、旋转变换.同样可得尺度函数系数的方程: 〈 ^N-R_Γ,I_mg〉 ≈(g_Γ/2^D-R)〈 ^N-D_Π(Γ),I_mg〉+h_Γ =(g_Γ/2^D-R)〈T ^N-R_Γ,I_mg〉+h_Γ (12)其中h_Γ为子树Γ的尺度函数系数的偏移量.由式(11)、(12),可以看出,分形块量化过程形成了一个从粗尺度小波系数到精细尺度小波系数的映射.还有,由式(12)可以看出传统分形编码方案中的偏移因子h_Γ只影响尺度函数系数.如图2所示,设X是I_mg的离散小波变换,较浅阴影的域子树S^N-D_Γ'X构成的码字g_Γ S^N-D_Γ'X来近似较深阴影的值子树S^N-R ΓX.于是: X= ∑ Γ∈  (S^N-R_Γ)^*(S^N-R_Γ)X≈ ∑ Γ∈  g_Γ(S^N-R_Γ)^* _P(Γ) ^D-R ·S^N-D_Π(Γ)X+ ∑ Γ∈  h_Γ(S^N-R_Γ)^*(S^N-R_Γ) l = A _WX+ B _W (13) 方程(11)和(12)表示小波和尺度函数ω_k∈W_N-R的系数是由经过平移后的粗尺度上的小波和尺度函数T_ωj的系数来表示的.在基W_N-R上展开内积Tω_j,得到T_ωj= ∑ ω∈W_N-R 〈 _k,T_ωj〉ω_k.于是式(13)中对应于基函数ω∈W_N-R矩阵 A _W的行向量的元素可表示为: 图1 图2 A _j,k=2^R-Dg_Γj,〈 _k,Tω_j〉 (14) 其中ω_j,ω_k∈W_R.首先考虑式(13)中矩阵 A _W的结构,将图像矢量 X 和 B _W进行重新排列,使它们按尺度函数系数和小波系数分组为( X )_、 B ^_W以及( X )_ψ、 B ^ψ_W,矩阵分块处理后成为: ( X )_ ( X )_ψ = A ^_W A ^ψ_W A ^ψ_W A ^ψψ_W ( X )_ X )_ψ + B ^_W B ^ψ_W (15) 其中所有 B ^ψ_W的系数都为零,因为 B _W的信息只依赖于图像的尺度函数系数.SQS量化算法去除了尺度函数系数(X)_对其他图像系数的依赖关系.于是 A ^_W、 A ^ψ_W和 A ^ψ_W的矩阵元素全为零.将式(13)改写为: X '= A _W(X')+ B _W (16) 其中 A _W= A ^ψψ_W, B _W= B ^_W, X '= X _ψ.将 X '的系数由粗到细按子树结构的顺序进行排列,并且只考虑非重叠域集的话,图像X'的变换矩阵 A _W可写成 N _D=2^2(N-R-1)个正方形子矩阵 A _i组成的一个块对角阵: A _W=diag( A _i) (17) A _i的构成如下: 1 2^D-R · g^lh_l1 0 … 0 0 0 … 0 0 0 … 0 0 γ^lh_l1 … 0 0 0 … 0 0 0 … 0             0 0 … γ^lh_l1 0 0 … 0 0 0 … 0 0 0 … 0 g^hh_l1 0 … 0 0 0 … 0 0 0 … 0 0 γ^hh_l1 … 0 0 0 … 0             0 0 … 0 0 0 … γ^hh_l1 0 0 … 0 0 0 … 0 0 0 … 0 g^hl_l1 0 … 0 0 0 … 0 0 0 … 0 0 γ^hl_l1 … 0             0 0 … 0 0 0 … 0 0 0 … γ^hl_l1             g^lh_l4 0 … 0 0 0 … 0 0 0 … 0 0 γ^lh_l4 … 0 0 0 … 0 0 0 … 0             0 0 … γ^lh_l4 0 0 … 0 0 0 … 0 0 0 … 0 g^hh_l4 0 … 0 0 0 … 0 0 0 … 0 0 γ^hh_l4 … 0 0 0 … 0 3×(4⁰+4¹+…+4^N-D)列             0 0 … 0 0 0 … γ^hh_l4 0 0 … 0 0 0 … 0 0 0 … 0 g^hl_l4 0 … 0 0 0 … 0 0 0 … 0 0 γ^hl_l4 … 0             0 0 0 0 0 0 0 0 0 0 0 γ^hl_l4 (18) 其中γ^o_ij=(g^o_Γ,g^o_Γ,g^o_Γ,g^o_Γ),Γ为下标(i,j)的缩写,0=(0,0,0,0),i∈{1,2,…,N_D},j∈{1,2,3,4},o∈Ω.因此只需要对{(g^o_Γ,Γ, i,B_W),i=1,2,…,N_D}进行编码就可完全定义变换T,其中 _i表示对矩阵 A _i所采用的仿射变换类型. 4 SQS算法中尺度函数系数对编、解码误差的影响 由前述分析,SQS编码可以用线性系统的动态方程进行完全描述.给定 A _W和 B _W,则输出就由初态和输入完全确定了.若给定一个系统,则它的稳态是由输入完全确定的,而与初态无关.由于稳态X_∞为T的固定点,有: X _∞= A _W X _∞+ B _W (19) 于是可直接求得: X _∞=( I-AW )^-1 B _W (20) 可见,系统的稳态是独立于初态且为 B _W的线性函数.IFS分形图像压缩编码算法是由Barnsley^[4]提出的拼贴定理来保证的,拼贴定理的核心就是为了设计一个IFS,使它的吸引子与原图的误差最小.然而该拼贴定理并不能保证解码误差一定小于拼贴误差,因为传统的拼贴定理所构成的IFS可能会由于迭代映射而使得解码误差变大了,即解码误差有可能大于拼贴误差.对此下面作详细分析.设X₀为编码原图像,定义: e_E=X₀-X₁,e_D=X₀-X_∞ (21) 有: e_E=X₀-(A_WX₀+B_W)=(I-A_W)X₀-B_W (22) e_D=X₀-(I-A_W)^-1B_W (23) 比较式(22)、(23)可得: e_D=(I-A_W)^-1e_E (24) 如果定义: M=(I-A_W)^-1 (25) 则X_∞=MB_W,e_D=Me_E,从而有: X_∞+e_D=M(B_W+e_E) (26) X₀=M(B_W+e_E) (27) 若定义: r=B_W+e_E (28) 则有 X₀=A_WX₀+r (29) 对比式(13)可以看出,A_WX₀表示了X₀的自相似分形变换编码分量,而r表示了X₀的残余分量,B_W则是送至解码器的r的近似值.若r在送入解码器过程中无任何误差,则: r=B_We_E=0e_D=0X₀=X_∞ (30) 图3