IFS中仿射变换的确定

D0I:10.13374/i.issm1001053x.2002.05.026 第24卷第5期 北京科技大学学报 Vol.24 No.5 2002年10月 Journal of University of Science and Technology Beijing 0ct.2002 IFS中仿射变换的确定 张亦舜杨扬 北京科技大学信息工程学院，北京100083 摘要针对一维直线上的有限点集，给出了构造相应函数的过程，从而将点集所对应的迭 代函数系统S)中仿射变换的系数求取问题转化为求解函数的极值点，然后将此方法推广到 二维点集. 关键词分形；吸引子；FS;自相似；仿射变换 分类号 TP391 分形几何学自70年代Mandelbrot提出以 变换w称为压缩变换，若对任意p,q∈X存在常 来，其理论和应用发展很快，尤其在图像图形学 数s,满足0<s<1,使得下式成立： 领域，分形的生成、图像的分形压缩得到了深入 d(w(p),w(q)≤sdp,q）, 研究.80年代中期，Barnsley基于局部与整体 故FS可记为： 自相似原理，提出了利用分形进行图像压缩的 {X;w,i=1,2,,n}. 方法，即迭代函数系统(Iterated Function Sys- 12压缩映射定理 tem),获得了很高的压缩比.但该方法在确定组 设{Xw,i=1,2,,n}是一个IFS,则存在一 成FS的仿射变换时有很大困难，需人机交互， 个惟一非空子集C,满足： 编码时间太长，压缩的效率取决于图像自相似 2w(C)=C. 江 性的程度及人为因素. C也称为此FS的吸引子，运用随机迭代算法可 根据FS理论，-一个FS确定一个点集，由 简便地在计算机上构造C,这相当于对C离散 随机迭代算法可简便地在计算机上画出这个点 化，此时得到的C是一个有限的点集. 集.因此，一个点集可由其对应的FS的仿射变 由上式得到，一个仿射变换a属于的FS的 换的系数编码，称为FS编码.但对任意给定的 必要条件是w(C)CC.进一步的了解可参考文献 点集，如何求取其FS编码，即自动而快速地确 [3-71. 定组成IFS的仿射变换系数仍是一个复杂而困 难的问题，至今没有有效的算法.本文提出了由 21 点集的函数构造 点集构造对应函数的一种方法，将此问题转化 2.1一维点集的函数 为求解函数的极值点. 设有计算机平面上一维有限点集C={a, i=1,2,,n以.为了便于讨论，设定C中元素为非 1IFS理论简介 负整数且存在整数p,q使p≤a,≤q,i=1,2,,n. 1.1定义 首先由集合C构造函数： 完备的度量空间(X,)以及n个压缩型的仿 (1 int(x+0.5)EC f(x)= 射变换wX一X一起构成一个迭代函数系统，简 (0int(x+0.5)C 称FS.一维时，仿射变换形如： 引进函数： H.x)=1.e 元r4e(e>0). w(x)=k-x+l; H(x)有性质： 二维时，仿射变换形如： limH.(x)dx=lim C 1 -xH9月 0πx+edt= x)b_0a<b<0,0<ab ella (1 a<o<b 收稿日期200107-12张亦舜男，37岁，博士 当e充分小时，H(x)衰减很快，如图1

第 24 卷 第 5 期 2 0 0 2 年 10 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n iv e r s iyt o f S e ic n e e a n d eT c b n o lO gy B e ij in g V6 1 . 2 4 N 0 . 5 o e t . 2 0 02 I F S 中仿射变换的确定 张 亦 舜 杨 扬 北京科技大学信息工程学 院 , 北京 1 00 0 83 摘 要 针 对一 维直线 上的有 限点集 , 给出了构造 相应 函 数 的过程 , 从而将 点集所对应 的迭 代函 数 系统 (I F s) 中仿射 变换 的系数求 取 问题转化为求 解 函数 的极 值点 , 然 后将此 方法推 广 到 二维 点集 . 关 键词 分 形 ;吸 引子 ; I F;S 自相似 ;仿射变换 分 类号 T P 3 9 1 分形几何 学 自 7 0 年代 M a n d e lb r o t ” , 提 出 以 来 , 其理论 和应用 发展很快 , 尤其在图像 图形学 领域 , 分形 的生成 、 图像 的分形压缩得 到了深人 研究 . 80 年代 中期 , B anr s l cy {21基 于 局 部与整体 自相 似原理 , 提 出 了 利用分形进行图像压缩 的 方法 , 即迭代 函 数 系统 ( tI e art e d Fun e t i o n s y s - et m ) , 获得 了很高的压缩 比 . 但该方法在确定组 成 IF S 的仿射 变换时有很大 困难 , 需人机交互 , 编码 时间太长 , 压缩 的效率取决于图像 自相似 性 的程度及人为 因素 . 根据 IF S 理论 , 一个 IF S 确定一个点集 , 由 随机迭代算法可 简便 地在计算机上画 出这个点 集 . 因此 , 一个 点集可 由其对应 的 IF S 的仿射变 换 的 系数编码 , 称为 IF S 编码 . 但对任意给定 的 点集 , 如何 求取其 IF S 编码 , 即 自动而快速地确 定 组 成 IF S 的仿射 变换 系数仍是一个复杂 而困 难 的 问题 , 至今没有有效 的算 法 . 本文提出 了 由 点集 构造对应 函数 的一种方法 , 将此 问题转化 为求 解函 数的极值点 . 变换 w 称 为压缩变 换 , 若 对任意 p , q 任尤存在 常 数 : , 满 足 Os< l< , 使得下 式成立 : d ( w 勿) , w (叮) ) ` s d勿 ,叮) , 故 IF S 可 记为 : {;X w , , i 二 1 , 2 , … , n } . 1 . 2 压缩映射定理 设 {;X w , , i 二 1 , 2 , 一 , n) 是一个 IF S , 则存在一 个惟 一非 空 子集 C , 满 足 : 乏w 义)C 二 .C C 也称 为此 IF S 的 吸引子 , 运用随机迭代算法可 简便地 在计 算机上构造 C , 这相 当于对 C 离散 化 , 此 时得 到的 C 是一个有 限的点集 . 由 上式得 到 , 一个仿射变换 众属 于 的 I F S 的 必要条件是 w( )C 〔 C . 进一步的了 解可参考文献 ( 3 一 7 ] . 1 I F S 理论简介 1 . 1 定 义 完备的 度量空 间 伏刃 以及 n 个压缩 型 的仿 射变换 w ` 火~ 矛一 起构成一个迭代 函数系统 , 简 称 IF S . 一 维时 , 仿射变换形如 : w (x ) 二 .k +x ;l 二维 时 , 仿射变换形如 : X( 、 f a b 、伏、 f e 、 W l l = 1 11 1+ ! 1 . 岁 户 、 c a 产岁 2 了 产 收稿日期 2 0 01 一7 一 12 张亦舜 男 , 37 岁 , 博 士 2 点集的函数构造 .2 1 一 维点集的函数 设 有计 算机平 面上 一维 有 限 点集 C 二 (风 , i 二 1 , 2 , 二 , n} . 为了便于 讨论 , 设定 C 中元素为非 负整数且存 在整 数 p , q 使 p ` 久 ` q , i = 1 , 2 , … , n , 首先 由集 合 C 构造 函数 : xf( ) 1 int x( +0 . 5 ) E C 0 i n xt( + 0 . 5 )睡C 引进 函数 : 、 卜十命 、 .) 从x( )有性质 : , . r b , r , 、 , , . r b l ￡ 1 11 1 . 了1 。 气X )几 t = l l fl l l — 一飞节 一 布Q 尤 = 。 一。 砂“ 一 、 一 。一 。 J 。 兀 r 十 c “ 、 . ￡ 1 ` f x 、} l l fl l— · — a I C [ a n l— 11 。 一。 兀 占 L 君 J I o a b< < 0 , 0 a< < b l a < 0 < b 当 。 充分小时 , 从 (x ) 衰减很快 , 如图 1 . DOI: 10. 13374 /j . issn1001 -053x. 2002. 05. 026

Vol.24 张亦舜等：FS中仿射变换的确定 ·579。 H.(x) H(x,)有性质： limlim广心H.x,y)drdy= I0其他 1a<0<b,c<0<d 1 e=0.2 构造函数： gx,八，a,b,c,d,e,f)= H..(x-(a.x+b.y+e).y-(c-x+d-y+S)) e=0.5 计算积分： S...(a,b,c,d,e,f)= 0 1 [Sg.(xv.a.b.cde-fxy)dxdy= 图1H(x)函数 Fig.1 H.(x)Function H..(x-(a.x,+b.y+e),y(c-x,+d-y.+f))dxdy. S.(a,b,c,d,e,f)是连续函数并有偏导数，且0≤ 构造函数g(x,k,D=∑H.(x-(ka+0),计算如 See(ab,c,d,e,f)≤n. 下积分： 与一维点集相同，若(au,b,co,d,e,6)是所 5.-)dxdw 求点集C的FS的一个仿射变换的系数，则有： 显然，S.(化，D是k,1的连续函数并有偏导数， limlimc)n, 且0≤S.(k,0≤n.若ko,o是点集C的IFS中一个 即limlim.S.(a,b,c,d,e,f,)在(ao,bo,c,d,eo,f6)存 仿射变换的系数，根据FS理论及随机迭代算 在最大值.故当e充分小时，连续函数S.(a,b, 法，a,∈C,3a,∈C,使k·a,+l∈(a-0.5,a+0.5) C,d,e,f,)在(a,b,ca,d,eo,)的邻域内存在最大 (在此不考虑k·a,+l=a,-0.5时的特殊情况). 值.可见确定点集C的FS的仿射变换系数转化 故 1img6x-ka+w》=1, 为求解S(a,b,c,d,e,f)的极值点. 因此 limS.(ko,lo)=n, 即limS.(k,)在(k,l6)存在最大值.所以当ε充分 3 实验结果 小时，连续函数S.(k,)在(k,l6)的邻域内存在最 求S,(化，)或S(a,b,c,d,e,f)的极值点，可以 大值.可见，确定点集C的FS的仿射变换系数 利用最优化理论中的多种算法.考虑到计算机 k,1转化为求解S.(k,)的极值点 平面上点的离散化引入的误差，在众多的极值 2.2二维点集的函数 点中，只有那些使limS.(k,)使或limlim.S.(a,b, E.s0乙=0 设有定义在计算平面p,q]×[r,s]上的点集 c,d,e,f)的值接近点数的极值点才有可能是需 C={(x,y),=1,2,,n},首先由集合C构造函数： 要的解.现在用如下两个仿射变换组成的FS 1(int(x+0.5),inty+0.5)》∈C 定义的cantor集来检验本文提出的方法. 八x)= 0其他 w(x)=0.33-x 引进函数： w2(x)=0.33·x+80 H.c(x,y)=- 图2是k固定取0.33，S.(k,0随1变化的情 (6,G,>0), (a -20020406080100 -20020406080100 图2Ss(0.33,)函数和S0.33,0函数.(a)e=0.5,k=0.33:(be=10,k=0.33 Fig.2 Sos(0.33,0)function and Si(0.33,/)function

V b l . 2 4 张 亦舜等 : IF S 中仿射 变换 的确 定 一 5 7 9 - 从 。 x( , 夕)有性质 : n 1 . 1 少`百. 卿卿厂 ! f 从 · (x, 夕 dx) 勿 - 构造 函数 : 其他 a <O <b . c < O< d 从 x( 、 . 、 多 ` x( , 夕 , a , b , c , d, e , f ) = 于从 · (x 一 .a( +xt ” · 对 一 以 , 一 .c( +xt “ 二 I 功 ), 君 二 0 . 5 计算 积分 : 及 去 ( a , b , c , d, e , f ) = 工 ` 方二 。 x( 少 , a , 。 , c ,试e刀 ; 粼:粼: 7 飞大必 dx 办 二 图 1 从 (x ) 函 数 F i g . l 从仕) F u n e it o n 构造 函数 吕 (x, k, l) = 艺从 x( 一 .k( 认+l )) , 计算如 下积分 : 及(k,l , 一 摆:胁 ,kl) · xf( dx) 一 鑫摆:必 ,kl) .dx 显然 , 及(k, l)是 凡 l 的连续 函数并 有偏导数 , 且 0 ` 叹(k, 乃` n . 若 k0 , 10 是点集 C 的 IF S 中一 个 仿射变换 的系数 , 根据 IF s 理论 及随机迭代算 法 , V ia 任 C , 日aj 任 C , 使 瓶 · 么十 10 任 a(j 一 0 . 5 , aj +0 . 5) (在此不 考虑 k0 · ia 十 10 二 马一 0 . 5时 的 特殊情况 ) . 故 因此 卿摆: 从(x 一侃时10 ) 一 ’ , lim 国(k0 , 10 ) = n , 从 ` 。 x( 一 a( · ix + .b iy + e) ,只c’ ix + .d 戈叮) ) d 不 4 F . 又 : , ( a , b , c , d, e , f )是 连续 函数并有偏导数 , 且O 二 及 声 、 ( a , b , c , 试 e , f )三 n . 与一维 点集相 同 , 若 ( a 。 , b 。 , c 。 , d0 , e 。 , 石)是 所 求点集 C 的 IF S 的一 个仿射 变换的系数 , 则有 : 卿卿又 一 ( a 。 , “ 。, c 。 , d0 , e 。 , 关) 一 ” , 即卿U孵 … ( a , b , c , d, e , f , ) 在( a 。 , b 。 , c0 , d0 , e 。 , 关)存 在最大值 . 故 当 。 充分 小 时 , 连续 函数民式 a , b, c , d, e , f , ) 在 (a0 , b0 , c0 , d0 , e0 , 关)的邻域 内存在 最大 值 . 可 见确定点集 C 的 IF S 的仿射变换 系数 转化 为求解又 、 ( a , b , c , 试 e , f , ) 的 极 值点 . 即l n l茂k( , l) 在 (k0 , l0) 存在最大值 . 所 以 当 。 充分 小时 , 连续函 数凡(k , l) 在 (褐 , l0) 的邻 域 内存在最 大值 . 可 见 , 确定 点集 c 的 IF S 的仿 射变换 系数 k , l 转化为求解 及k( , l) 的极值点 . .2 2 二 维点集的函数 设 有定义在 计算平 面 叻 , 创 ` 叶 , : 〕上 的 点集 c 一 {x(, , 升) , 户 1 , 2 , … , n} , 首先 由集合 c 构造 函 数 : f( x , y ) 引进函 数 : 从 。 、 (x , ! ’ (` n `(x + o · 5 ) , ` n `份0 · 5 )) 任 C {0 其他 3 实验结果 求叹执 l ) 或又 。 ( a , b , c , 试e , f ) 的极 值点 , 可 以 利用 最优化理论 中的 多种算法 . 考虑 到计算机 平面上 点 的离 散化引人 的误差 , 在 众多 的极值 点中 , 只 有那些使 h n l 国( k , l) 使 或 h m h ll l 国汉 a , b, `一 O 乙 一 O` 一 O c , d, e , f ) 的值接近点数 的极 值点才有可 能是需 要 的 解 . 现在 用 如下 两个仿射变换组 成的 IF S 定 义 的 ca nt or 集来检验本 文提 出的方法 . ! w , x( ) 一 O · 3 3 ’ ` } w Z x( ) = 0 . 3 3 · x + 8 0 尽 犷十心 君, 犷+ 式 (凡 , ￡。 > 0 ) , 图 2 是 k 固 定取 .0 3 , 及k( , l) 随 l 变化 的情 ǎ、材à时 à(I蔺时 一 2 0 0 2 0 4 0 6 0 8 0 1 0 0 一 2 0 0 2 0 4 0 6 0 8 0 1 0 0 图 2 50 3 ( 0 · 3 3 , l) 函 数和 况 。 ( 0 · 3 3 , )I 函 数 . ( a ) : = 0 · 5 , k = 0 . 3 3 ; ( b ) : 二 1 0 , k = 0 . 3 3 F ig . 2 50 . 5 ( 0 . 3 3 , 1) fu n e t i o n a n d 昌 。 (0 . 3 3 , 乃fu n c t i o n

·580· 北京科技大学学报 2002年第5期 况.图3是1固定取80，S.(k,)随k变化的情况. 许多极值点会消失.本例中，即使当ε二10时，在 图中可见，S(k,)的确在(0.33,0)和(0.33,80)存在 点(0.33,0)及(0.33,80)仍然存在极值点或极值 极值点，也可以说是最值点.同时还看到，ε取定 点在此附近.因此调整ε的取值，可以加快求解 不同值时，极值点的数目差别很大，当ε增大时，所需S.(k,)极值点的速度 (b) 0.0 0.10.20.30.40.5 0.0 0.10.20.30.40.5 k 图3Ss(k,80)函数和S1(k,80)函数.(ac=0.5,1-80;(b)c=10,1=80 Fig.3 S(k,80)function and S(k,80)function 4 结论 [M].BYTE,1988 3 Welstead S.Fractal and wavelet image compression tech- 本文提出的将仿射变换系数的确定转化为 niques [M].SPIE Press,1999 求函数极值的方法，为仿射变换的自动求取，从 4陈守吉，张立明.分形与图像压缩M).上海：上海科技 而为给定点集的FS的自动确定指出了一条途 教育出版社，1998 径.但此方法还有一些困难，最主要的是运算量 5 Falconer K.分形几何M).沈阳：东北工学院出版社， 1991 较大，特别在二维时，涉及到6个参数的变化. 6金以文，鲁世杰.分形几何原理及其应用M江苏： 由于ε的取值对运算量影响很大，ε值太小，会 浙江大学出版社，1998 产生许多无用的极值点；ε值太大，需要的极值7曾文曲，王向阳.分形理论与分形的计算机模拟M 点也可能消失，因此，如何取适当的ε值值得进 沈阳：东北大学出版社，1993 一一步深入研究 8 Kya B,Yang Y.Optimization of fractal iterated function system (IFS)with probability and fractal image gener- 参考文献 ation [J].J Univ Sci Technol Beijing,2001,8(2):152 1 Mandelbrot B.大自然的分形几何学（中译本）M.上 9 Kya B,Yang Y.Imporove fractal compression encoding 海：上海远东出版社，1998 speed using freature extraction and self-organization net- 2 Barnsley MF,Sloan A D.A better way to compress images work [J].J Univ Sci Technol Beijing,2001,8(4):306 Determination of Affine transform of IFS ZHANG Yishun,YANG Yang Information Engineering School,UST Beijing,Beijing 100083,China ABSTRACT The Iterated Function System(IFS)is an important theoretic and applied branch of fractal ge- ometry.An IFS defines a point set called the attractor,but there have not any effective methods to obtain the corresponding IFS of a given point set.This paper first proposes an approach to constructing a function for a finite point set defined on the one-dimensional line,so the problem of determining the coefficinets of the affine transformation in an IFS is transfered into determining the extreme points of a the function.This method is then,extended to the two-dimesional plane. KEY WORDS fractal;attractor;IFS;self-similarity;affine transformation

一 5 8 0 · 北 京 科 技 大 学 学 报 20 0 2 年 第 5 期 况 . 图 3 是 l 固定取 80 ,及k( , l) 随 k 变化 的情 况 . 图 中可见 , 凡(k, l )的确在 ( 0 . 3 3 , 0 )和 ( 0 . 3 3 , 8 0 )存 在 极值点 , 也可 以说是最值点 . 同时还看 到 , : 取定 不同值时 , 极值点 的数 目差别很大 , 当 : 增大时 , 许多极值点会消失 . 本例 中 , 即 使 当 二10 时 , 在 点 ( 0 . 3 3 , 0 )及 ( 0 . 3 3 , 8 0 ) 仍然存在极 值点或极值 点在此 附近 . 因此调整 : 的取值 , 可 以加快求解 所需及k( , O 极值 点的速度 . ǎù矿à时 弓(I时 土.0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 k k .s j (k, 8 0 ) 函 数 和 5 1。 (k, 8 0 ) 函数 . ( a ) ￡ “ 0 . 5 , 卜8 0 : ( b ) 。 二 1 0 , l = 8 0 F i g . 3 OS , (介 , 8 0 ) ur n e ti o n a n d s ,。 k( , 8 0) fu n e t i o n 飞口 n ù刁 nU工别`l 4 结论 本文提出的将仿射变换系数 的确定转化为 求 函数极值 的方法 , 为仿射变换的 自动求取 , 从 而 为给定点集 的 IF S 的 自动确定指 出了一 条途 径 . 但此方法还有一些困难 , 最主要 的是运 算量 较 大 , 特别在 二维 时 , 涉及 到 6 个参数的变化 . 由于 : 的取值对运算量影响很大 , : 值太小 , 会 产生许 多无用 的极值点 ; ￡ 值 太大 , 需要的极值 点 也可 能消失 , 因此 , 如何取适 当的 。 值值得进 一 步深人研 究 . 参 考 文 献 1 M a n d e lb r o t B . 大 自然 的分形 几何学 ( 中译本 ) [M ] . 上 海: 上海 远东 出版社 , 19 98 2 B am s l e y M E S l o an A D . A b e t e r w ay t o c o m Per s s im a ge s [M l . B Y ET , 1 9 8 8 W 七l s t e a d 5 . F r ac t a l an d w va e l e t i m ag e e o m Per s s i o n t e e h - n iq u e s [M ] . S P IE P r e s s , 1 9 9 9 陈守 吉 , 张立 明 . 分形 与图像 压缩M[ 1 . 上海 : 上海科 技 教育 出版 社 , 1 9 98 aF ic on er K 分形 几何 〔M ] . 沈 阳 : 东北 工学 院 出版社 , 1 9 9 1 金 以文 , 鲁世 杰 . 分形 几何原理 及其应用 [M ] . 江苏 : 浙 江大学 出版社 , 19 9 8 曾文 曲 , 王 向阳 , 分 形理 论与 分形 的计算 机模拟 [M 』 . 沈 阳 :东北 大学 出版社 , 1 9 93 K y a B , Y自n g .Y O P ti m i z at i o n o f afr e at l i t e art e d fu n e ti o n s y s t e m ( IF S ) w i th P r o bab i liyt a n d fr ac at l im a g e g e n e r - a ti o n [J] . J U n i v S e i eT e hn o l B e ij i n g , 2 0 0 1 , 8 ( 2 ) : 1 5 2 K y a B , 、 触n g 丫 Im P o or v e far c t a l e o m Per s s i o n e n e o di n g sP e e d u s i n g fr e a t u r e e Xtr ac t i o n an d s e l-f o gr an i z at i o n n e t - w o kr [J] . J 饰i v S e i eT e hn o l B e ij i n g , 2 0 0 1 , 8 ( 4 ) : 3 0 6 D e t e n n i n at i o n o f A m n e tr a n s fo n n o f IF S 乙阮理刃G 几h u n , YA N G aY n g I n of rm at i o n E n g l n e e ir gn S e h o o l , U S T B e ij in g , B e ij i n g 10 0 0 8 3 , C h i n a A B S T R A C T T h e It e ra t e d F un c t i o n S y s t e m ( I F S ) 1 5 an im Po rt a l l t t h e o r e t i c an d a PPli e d b r a n e h o f fr a e t a l g e - o m e try . A n I F S d e if ne s a Po int s e t e al l e d hte a t r ac to r , b ut t h e r e h va e n o t a n y e fe c t i v e m e ht o ds t o o bt a i n ht e e o r e s Pon d i n g I F S o f a g iv en Po int s et . T h i s Pap e r if r s t Pr op o s e s a n a PP r o a e h t o e o n s tur e t i n g a fu n e t i o n fo r a if n it e P o iin s e t de if n e d o n ht e o n e 一 d im e n s i o n a l li n e , 5 0 ht e P r o b l e m o f d e t e mr i n ign ht e e o e if e i n e t s o f th e a if n e tr an s fo mr at i o n i n an IF S 1 5 tr an s fe r e d int o de t e mr i n i n g ht e e x etr m e Po int s o f a het fu n e t i o n . Th i s m e ht o d 1 5 th e n , e Xt e dn e d t o ht e wt o 一 id m e s i o n a l Plan e . K E Y WO R D S afr e t a l: a t r a e t o r : IF S : s e l-f s im il ar iyt : a if n e tr an s fo mr a t i o n