基于Penrose铺砌的数字图像重要性采样算法

姜玲燕， 祝敏华， 杨 欢

(1. 苏州幼儿师范高等专科学校 基础部， 江苏 苏州 215000;2. 中国电子科技集团公司五十二研究所， 浙江 杭州 310000;3. 南京晓庄学院 教师教育学院， 江苏 南京 211171)

0 引言

图像作为人类获得直观信息的重要载体之一， 具有信息量大、细节信息丰富、易于理解等特性， 已深入人类的生活、学习和工作. 随着科技进步， 人们获得的数字图像精度越来越高， 但受限于带宽和存储容量， 这些高精度图片却无法满足虚拟现实、电子游戏及数据可视化的实时性需求. 数字图像采样技术通过降低数字图像数据量来提升图像传输速率， 满足实时性要求.

采样技术始于上世纪50年代， 并在八九十年代得到了较快的发展. 1955年， G.Franklin[1]提出了简单均匀采样法， 但该方法所获得的采样点数量会随着图像像素梯度变化剧烈程度的提高而减少， 导致采样点集冗余、细节丢失严重; Brown[2]提出了易于实现的随机抖动采样法，由于采集的数据完全随机， 并不利于图像重建; 为避免出现上述问题， 诸多抖动采样算法应运而生， 如1980年Latin[3]首先将采样区间划分为n×n个子空间， 然后运用基于数学过程方法(如Hammersley 序列[4]) 完成简单采样， 最后利用Halton序列[5]进行采样分析算法; Ulichney[6]提出了能有效防止重建图像走样的蓝噪声采样算法; Mccool[7]则利用若干个圆形来控制采样范围， 从而避免采样点过于密集， 确保其分布相对均匀; 随后， Lagae[8]、Dunbar[9]等提出了基于边界的采样技术， 但此类技术未考虑采样密度的平滑过度. 国内对于采样技术的相关研究则多聚集在通信领域， 付妍等[10]提出使用Penrose铺砌的采样技术来适应圆形参数域的重要性采样三维模型网格重建; 陶会强[11]利用RosenBlatt变换来构造随机的采样点集， 提出随机化拟重要性重采样算法.

以上采样算法并不能根据图像的特性调整采样点的密度，采样自适应性及均衡性较弱.本文在研究Penrose铺砌[12， 13]的基础上， 提出一种自适应性非周期铺砌的数字图像重要性采样算法. 实验证明， 该算法能有效控制采样精度且效率高、稳定性好，采样点集的分布更符合原始图像特点.

1 算法描述

本文的采样算法主要分为数字图像采样点集的生成和优化两个阶段， 其中采样点集的生成阶段主要包括如下两个步骤:

(1) 建立初始铺砌. 改进Penrose铺砌的胖瘦菱形并组合变换得到6种多边形对图像进行初始铺砌.

(2) 铺砌的自适应细分. 根据数字图像的重要性分布及相应的细分规则对初始铺砌进行自适应细分， 达到相应的细分要求后则终止细分， 得到初始采样点集.

为滤除采样过程中产生的噪声并使采样点分布更加均匀合理， 需要对采样点集进行优化. 这一工作由采样点集的优化阶段来完成， 主要包括以下两个步骤:

(3) 滤除采样噪声. 利用斐波那契码[14，15]对细分所得到的采样点进行定位， 并将斐波那契数列转化为一个整数， 若这一整数大于待采样图像的局部灰度值， 则作为采样点输出， 反之则作为噪声点滤除.

(4) 优化采样点集分布. 根据斐波那契码前六位及待采样图像局部灰度值建立矫正模型， 并根据这一模型计算采样点的位移量; 根据细分图形的标记点确定采样点的位移方向， 从而得到优化后的采样点集.

2 采样点集生成

为了得到合理的采样点， 本文利用改进的Penrose铺砌多边形对图像进行细分， 在每一个细分区域中进行采样， 从而得到初始的采样点集.

2.1 建立初始铺砌

1974年， 俄罗斯数学物理学家Roger Penrose[16]提出Penrose铺砌: 利用若干种多边形按照既定规则非周期性的铺满整个平面， 这种铺砌可以无限延伸且具有自相似性(即在一定区域内不会出现大面积的相似图形). 按照铺砌的基本图形可将Penrose铺砌分为3类: 第一类， 利用正五边形、五角星形、船形(3/5五角星)和菱形(最小角为36°)4种基本图形进行铺砌; 第二类， 利用风筝(四个角度分别为72°、72°、72°和144°)和飞镖(四个角度分别为36°、72°、36°和216°)形状的多边形所组成的图形进行铺砌; 第三类则利用胖菱形(大小角分别为108°、72°)、瘦菱形(大小角分别为144°、36°)进行铺砌， 三种类型的基本图形及其按照相应规则进行铺砌的效果如图1所示.

图1 三种Penrose铺砌基本图形与效果图

本文利用第三类Penrose铺砌对数字图像进行分割， 由于胖瘦菱形在变换过程中， 会过度扩张且易产生重叠区域， 并不完全适用于数字图像的铺砌， 因此需要改进基本图形胖菱形和瘦菱形， 具体方法如下:

(1) 将胖菱形和瘦菱形沿着对角线平分成2个三角形，如图2所示;

图2 胖菱形(左)、瘦菱形(右)分割图

(2) 给原始胖菱形和瘦菱形每个顶点位置添加两种标记点a、b， 这两种点标记位置即为采样点集的位置; 为了方便观察改进之后的Penrose细分，特意将标记点a，b用正五边形表示.改进后多边形中的标记点a和b的形状可以忽略，因为a，b 两个标记点只记录需要产生采样点的位置，且不再细分，只改变方向.

(3) 每个多边形的方向由图3中标记点a、b的两个箭头所形成的正交向量所决定.

图3 修改之后第三类Penrose铺砌的细分规则

2.2 自适应细分

由于图像灰度变化越剧烈的区域细节越丰富， 为保证采样的精度， 本文算法根据图像灰度变化的剧烈程度确定图像的重要性分布程度， 使Penrose铺砌能根据图像特征进行自适应的调整， 从而产生采样点的自适应分布.

确定自适应细分的规则之后， 还需要确定自适应细分的程度， 即细分到何种程度停止. 由于Penrose铺砌的自适应细分是在局部进行的， 即对当前多边形P细分时， 会在P的内部产生多个多边形P1、P2、P3…Pn，如图4(b、c)所示，红色胖菱形标注的区域，多次细分后，在图4(b)的红色区域内部进行细分得到图4(c)的红色区域， 下一次细分操作需要在每个新产生的多边形内部分别进行局部细分. 在细分过程中记录生成的多边形Pm的细分级别Lm， 并在后继的细分过程中， 计录当前多边形的细分次数Nm， 一旦Nm=Lm， 就表示完成Pm的自适应细分. 其中，Pm的细分级别Lm是根据当前多边形区域内图像的重要性值计算的， 具体计算公式如下：

(1)

图4 Lena原始图像及不同mag值下改进的Penrose铺砌效果图

3 采样点集优化

由于利用改进的Penrose铺砌进行自适应细分得到的采样点位置对于细分的基本多边形而言是相对固定的， 且在采样过程中可能会产生噪声， 因此为了使采样点更加符合图形的纹理分布， 需要对原始采样点集进行去噪和优化.

3.1 采样点集去噪

利用改进后的Penrose铺砌对图像进行非周期的自适应铺砌后， 会产生大量的标记点即采样点a、b. 由于局部铺砌的细分程度受待采样图像局部区域的mag值控制， 因此细分程度和采样点的数量会随着区域灰度值的大小而相应增多或减少.

但是采样点位置所对应的待采样图像的灰度值可能并不是计录细分次数时的合理值(合理值是指该点位置的灰度值计算出来的细分级别能够使该区域的多边形继续细分)， 导致采样过程中产生噪声点.

表1 Penrose多边形细分过程中“斐波那契码”的分配规则

为避免产生大量的采样噪声， 本文引入“斐波那契码”[19，20]数字编号系统来控制采样点的密度: 在进行细分过程中， 为每个多边形分配一个“斐波那契码”(简称F码). 整个细分过程F码的分配规则如表1所示，其中， a#的表示多边形a的F码为#. 在细分之前， 先用符号#代替当前多边形的F码， 每次细分时， 在当前多边形的F码前面添加2位二进制编码形成细分之后多边形的F码. 因此， 经过n次细分之后， 多边形的F码长度将达到2n位. 斐波那契数列系统可将F码转化成一个整数， 任意一个整数n在该系统中都可以表示为它的斐波那契数Fi乘以它的位置系数的总和. 这个转化过程如公式(2)所示:

(2)

F0=0,F1=1,F2=1,F3=2,F4=3,F5=5,F6=8, …

(3)

由公式3可知F1=F2=1， 为保证Fi的唯一性， 本文从i=2开始计数，如式(4)所示:

(00001)F=1, (00010)F=2, (00100)F=3, (00101)F=4, (01000)F=5, (01001)F=6, (01010)F=7, (10000)F=8, (10001)F=9, …

(4)

由于在Penrose多边形递归细分过程中， 不同的多边形所添加的二进制编码是不同的， 因此， 细分后所得到的Fi也不同的: 分配给标记点a、b的F码所对应的整数都在范围[1，F2(n+1)-1]中， 其中n为最初多边形的细分次数，Fi为该标记点位置上采样点的密度阈值.在输出标记点之前， 将该点位置原始图像的重要性密度值I(x， y)与其密度阈值Fi进行比较， 若I(x， y)大于Fi则将该点作为采样点输出， 反之则作为噪声点滤除.

3.2 采样点集优化

经过多边形自适应细分后形成的标记点a、b决定了采样点的位置， 由于采样点是根据多边形自适应细分之后形成的非周期铺砌中的标记点a、b的位置生成的， 因此采样点的位置于与细分的多边形相对固定，为了获得分布效果更好的采样点集， 需要对采样点集进行优化.

为了使采样点集的空间分布更加合理， 本文根据F码前六位及待采样图像局部灰度值创建矫正向量表， 矫正向量跟非周期铺砌中的每个基本多边形的方向相关， 采样点根据该表计算所得位移量、当前基本多边形的方向进行合理的移动， 从而使采样点的分布相对均匀. 改进后的Penrose铺砌具有非周期性， 直接计算矫正向量会降低算法运行的效率， 本文利用Penrose铺砌的自相似性， 将矫正向量的数量控制在固定范围内， 从而降低计算矫正向量的时间复杂度: 利用多边形所包含的F码的前六位计算得到Penrose铺砌中基本多边形结构索引Is， 由公式2、3可知， F码的前六位可转换得到21个结构索引.

采样点的分布是根据非周期铺砌进行层次性细分而得到的， 细分次数越多， 采样点的细分层次就越大， 随之采样区域也越小. 因此在进行采样点修正时， 这些采样点的移动距离也相应变小.对于两个处于同一细分层次的采样点来说， 它们所处位置的重要性密度值可能不同， 甚至相差很大. 如果仅根据细分层次来确定矫正向量的偏移量， 可能会造成采样点位移量过大或过小， 产生误差. 因此本文根据原始图形的重要性密度值来划分矫正向量的层次， 即重要性索引Iv， 其计算如公式(6)所示：

(5)

Iv=⌊n×Φ(mag×I(x, y))⌋

(6)

图5 Φ(x)函数

其中， 符号⌊ ⌋表示向下取整;mag为原始图像的重要性密度值缩放因子;I(x， y)为当前图像区域上坐标位置为(x，y)的像素点的重要性密度值;n为重要性索引的最大值， 也是矫正向量划分的最大层次;Φ(x)函数将一个实数映射到[0， 1]范围内， 如公式(5)所示.公式(6)将重要性索引值控制在[0，n]的范围内.图5显示了函数Φ(x)在二维坐标空间中值的分布， 由图6可知， 当n=8时， 重要性索引值的分布最均匀， 因此本文设定Iv所在区间为[0， 8].根据重要性索引值Iv(范围区间[0， 8])和结构索引值Is(范围区间[0， 21])建立矫正向量表(8×21的二维数组)， 矫正向量表中的每一项都保存了矫正向量的偏移量.在进行采样点的纠正时， 采样点的移动方向为当前标记点a、b的正交向量方向， 移动大小为矫正向量表中对应的值与当前方向缩放系数的乘积.

4 实验结果及分析

我们利用VC++6.0和OpenGL在PC机实现了本文数字图像采样技术， 实验表明本文提出的基于Penrose铺砌的数字图像重要性采样技术在降低图像数据量的基础上能获得质量较高的采样点集.

本文算法可根据用户需求， 交互调整mag值， 从而得到精确度不同的采样图像， 如图6所示:mag值越大获得的采样点数量越多、细节信息越丰富， 采样效果图便越接近原始图像.同时， 本文的采样技术与光线跟踪采样算法、结构化重要性采样算法相比效率更高、采样点更符合原始图像特征， 如图7所示.

图6 不同mag值下Lena采样效果图及采样点数量(S)

图7 采样点为300， 效果对比图及用时(T)

5 结语

本文提出了一种基于Penrose铺砌的数字图像重要性采样技术， 其主要特点如下:(1)利用改进的胖瘦菱形对数字图像进行原始铺砌， 通过调整原始图像的重要性密度值的缩放因子mag， 使得在原始铺砌的基础上根据数字图像的纹理特征进行自适应细分， 从而得到初始采样点;(2)利用“斐波那契码”对自适应细分过程中的多边形进行编号， 将当前标记点位置所对应的原始图像重要性密度值与当前采样点的密度值进行比较， 滤除采样时产生的噪声;(3)根据矫正向量表调整采样点的位置，从而使采样点集空间分布更符合图像特征， 提高采样质量.

今后考虑在进一步提高采样精度的基础上研究该类采样方法， 使计算机自动调整缩放因子mag， 在采样精度和采样数据量之间取得较好的平衡是未来研究的方向.