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