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,满足00). 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其他 1a0), (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 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