2.3 分形图像编码方法

2.3.1 Jacquin的分形图像编码算法

Barnsley首先提出了静态数字图像的压缩算法。其算法的步骤为：把原图预分解为若干个分形的子图，使每个子图具有一定的分形结构（子图的整体与局部之间存在某种自仿射特征），分解可采用其他的图像处理手段，且由这些大量的子图组成了分形库，每个子图可在这些分形库中找到它们的匹配子图编码。这样，对图像的分形编码可化为图像分割，到库中找匹配子图的编码，最后扔掉原图，保存子图编码，进行存储或传输。

从目前来看，Barnsley的方法存在很大的问题。因为对于图像的子图分割本身，还没有一种计算机自动分割的方法；其次分形库的规模大，没有统一的建库方法；高压缩比编码搜索的过程是以费时费力为代价的，难以实现自动压缩。有效的方法至少目前没有公开。

A.E.Jacquin[2.18]提出的全自动的分形图像压缩方法是以局部的仿射变换代替全局的仿射变换，采用基于图像划块的方式实现的。

多数灰度图像并不存在整体的自相似性，只能利用局部自相似性来求出仿射变换系数，以达到压缩目的。

不失一般性，下面讨论正方形的数字图像A，它有2N 2N× 个像素点，其(f(i, j),i, j)被量化为256个灰度级fk(i,j)，0 ≤k ≤255。把图像分割成n个子块Ri（i=1,2,…,n），它的尺寸为2R 2R× ，i 代表子块的编号；有Ri∩Rj=φ，i≠j；。让Dj代表比Ri大的尺寸的图像子块，2D ×2D，D＞R，Di∩Dj ≠φ,j=1,2,…,(2N-2D+1)×(2N-2D+1) 。自相似性的匹配在Ri与Dj之间进行。由于Dj，Ri比整个图像小得多，只要子块划分的足够小，局部自相似性在图像中总是存在的。整个编码过程如图2.4所示。

为了以后证明的方便，定义一些操作符如下。

“取块”操作符，它作用于图像A 后表示在有灰度的图上取出一个三维的块，其底的大小为2J ×2J，其第三维，即灰度函数，取块连同2J ×2J的底一起取出来。K,L表示子块在二维底部左上角的位置，坐标为(K,L)。

“放块”操作符，A表示把底部2J ×2J的三维块插入全0的图中，且插入子块的左上角位于(K,L)上。

“平均-抽样”操作符Aν，把2J ×2J带有灰度的图像通过近邻的四个像素点灰度求平均-抽样，变成2J-1×2J-1尺寸的块。Aν操作可用下式表示：

通过Aν操作，2J ×2J的图变为2J-1×2J-1尺寸的块。其灰度函数的分辨率也减小了，即图像变粗糙了。

“反射-旋转”操作符Lp，是表示块的旋转变换，犹如IFS变换中的系数a、b、c、d，为了简化匹配，把一个正方形子块的旋转化为最简单的8种方式，即旋转0°、90°、180 °、270°垂直中线反射、水平中线反射和两个对角反射这8种固定方式，p=8。

设Dj是一个图像块，它的灰度函数为{uj(ix,ij):i,ij=0,1,…,2D-1}，对应的8种变换为

L1：uj(ix,ij)=uj(ix,ij)，旋转0°。

L2：uj(ix,ij)=uj(ix,2D-1-iy)，垂直中线反射。

L3：uj(ix,ij)=uj(2D-1-ix,iy)，水平中线反射。

L4：uj(ix,ij)=uj(iy,ix)，对角线ix=iy反射。

L5：uj(ix,ij)=uj(2D-1-iy,2D-1-ix)，对角线ix+iy=2D-1反射。

L6：uj(ix,ij)=uj(iy,2D-1-ix)，旋转90°。

L7：uj(ix,ij)=uj(2D-1-ix,2D-1-iy)，旋转180°。

L8：uj(ix,ij)=uj(2D-1-iy,ix)，旋转270°。

利用上面定义的操作符，块与块之间的自相似性的搜索是去找一个近似的匹配，即

式中，CK,L是位置（K,L）子块的变换伸缩因子；hK,L是它的偏移量；I 是2N × 2N的全1矩阵；H(K,L)表示从位于（K,L）位置上的子块映射到其对应的父块位置；P(K,L)表示对位于（K,L）上的子块的8种变换。

编码的过程是：

① 将图像A分解为互不交叠的子块Ri，每个Ri块可用“取块”得到，符号为A。

② 搜索与其相似的父块Dj，并对父块做缩小、旋转和平移，父块的取块变换符号为LP(K,L )AνA，通过Aν后父块与子块有相同的尺寸。

③ 如果 A和LP(K,L)AνA各像素点上的灰阶值分别为a1,a2,…,am、b1,b2,… ,bm，则式（2.6）两边近似的误差可用式（2.7）表示：

搜索过程就是选择H(K,L)和P(K,L)，使dp达到最小，即利用对式（2.7）求导而得系数CK,L和hK,L。令∂dp/∂CK,L=0，∂dp/∂hK,L=0，得

且当时，CK,L=0，

此时，有

④ 对每一个子块Ri，改变H(K,L)和P(K,L)，找到一个最优匹配映射父块Dj，使dp达到最小，则记下CK,L和hK,L，H(K,L)和P(K,L)，就完成了一个子块Ri的编码。

⑤ 对所有子块，都分别寻找其对应的父块，使图像A上的每一子块Ri，都用其父块来覆盖，就完成了整幅图像的编码。图像的解码，是通过式（3.7）的迭代：

式中，RI表示图像中所有子块集。图2.5显示了Jacquin编码后图像迭代一次、两次和十次的结果。

2.3.2 Fisher的自适应四叉树分形图像编码算法

采用Jacquin的方法可以使编码全自动进行，但是分块搜索需要的计算时间相当可观。一幅2N ×2N像素点的灰度图像A，被划成尺度为2R ×2R像素的子块Ri，则A包括的子块数为

对每个可能搜索的最大自相似块Dj的数为(2N-2D+1)× (2N-2D+1)，如果采用8种“反射-旋转”的变换，对每个Ri必须有8×(2N-2D+1)×(2N-2D+1)次匹配计算才能找到一个最优编码参数CK,L,hK ,L，其搜索的量级为ο((2N)3)～ο((2N)4)。为了降低分形编码时搜索的复杂度，许多文章提出了一些改进方法，其中Fisher[2.3][2.21]的四叉树方法是目前分形图像编码中最主要的算法之一。

Jacquin方法中的父块和子块，都是固定尺寸的，父块和子块的尺寸，对于分形图像编码的质量和压缩比的影响很大。如R,D很大，父块库中父块数目比较少，很难找到父块与子块之间的相似关系，即使求出最优匹配系数，但原图A与拼贴一次仿射变换后的图的误差很大，将来的解码图像质量也很差；但如果R,D尺寸很小，那么总可以找到非常好的自相似匹配系数，此时图像编码的仿射变换数目剧增，并不能达到图像压缩的目的。

Fisher和Jacquin等人提出根据允许的误差ε而改变子块和父块的尺寸大小的做法，能对于大尺寸的子块和父块之间的相似性合理的选取仿射变换系数，而对于大尺寸达不到要求的子块，改变其边长，从2R到2R-1, 2R-2，…，相应的父块也可同时缩小，父块与子块之间的匹配尺寸是以要求误差ε和压缩比来进行的，这种方法称为四叉树的自适应方法。

设ε为一个分形压缩编码过程中，父块与子块之间匹配的允许误差，和分别为最大子块边长和最小子块边长，能达到压缩的最小子块尺寸为。

① 原始图像A，分割成不相交叠的的子块Ri作为初始的分割，Ri的左上角位于（K,L）的位置上，用取块符A表示。

② 搜索其相应的父块，位置在π(K,L)上，采用“反射-旋转”操作，和平均抽样操作搜索的相应父块为LP(K,L)AvA。设子块与变换后的父块的灰阶分别为a1,a2,…,am和b1,b2,…,bm。子块与变换后的父块之间的误差为

令∂dp ∂CK,L=0，∂dp ∂hK,L=0，求出，，按下式计算出。

③ 如果，则记下(K,L), π(K,L),P(K,L), , ，就完成了对Ri的编码，否则，转到④。

④ 如果，则把子块Ri再划分为四块，父块也相应划分为四块，此时取t=t + 1，子块仍用A表示。对父块的变换相应的为LP(K,L)AvA，继续采用式（2.7），此时

这里的bi′, ai′都是在四叉树划分时块中的灰度值，并再按式（2.8）求出。

⑤ 重复③和④，直到所有的大小子块与相适应的父块之间自相似变换误差都小于ε为止。

以上两方法分别的解码结果分别如图2.6和图2.7所示，其压缩比分别为25.913和27.389。