离散可分离剪切波变换(DSST)及其数值计算

离散可分离剪切波变换及其数值计算1、离散可分离剪切波变换DSSTWang-QLim在2010年提出了离散可分离剪切波变换（DiscreteSeparableShearletTransform，DSST），其中一个主要特征就是可以选择可分离的尺度函数22LR及剪切波生成函数(0)22LR（(1)22LR），即函数可表示为1212,xxxx，(0)121112,xxxx，(1)(0)1221,,xxxx下面将在水平锥0C上构造可分离剪切波生成函数22LR以及与之相关的尺度函数22LR，垂直锥1C同理。令2LR是一维紧支撑尺度函数，并选择某个相适的滤波器h（所需条件将在后面讨论）使其满足：1111111()()2(2)nxhnxnZ（1）如果与之相关的一维紧支撑小波函数2LR，可用相适的滤波器g表示为：1111111()()2(2)nxgnxnZ（2）那么，此剪切波生成函数可表示为121112,xxxx（3）尺度函数可表示为121112,xxxx（4）对于固定的J0，假设函数22fLR可表示为1122222,2JJJJnfxfnxnxnZ（5）这是一个数字实现的常规假设，尺度系数可被看做f的抽样值，事实上，通过选择合适的可使2JJfnfn。由上面的讨论，可知剪切波系数,,,0,1jkmfjJ可通过下式计算,,2,0,2,,jkmjjmkffS（6）若2j不为整数，则需选取22jj或。式（6）显示了剪切波系数,,,jkmf的离散化方法：首先应用与各向异性抽样矩阵2j相关联的离散可分离小波变换计算22jkfS。与式（5）定义的假设形式f相比，要求22jkfS包含在以下尺度空间中2121222,2:,JJJJVnnnnZ由上式很容易看出，如果剪切系数22jk为非整数，则剪切矩阵22jkS不能将规则网格22JZ保留在VJ中，即2222jkSZZ为了解决这个问题，定义一个新的尺度空间4222,121222,2:,kJjJjJJjJkVSnnnnZ可以看出由仿射规则网格22JZ沿着水平方向以22j为因子，可得到尺度空间2,kJjJV。基于这种改变，新网格222JjJZZ在剪切算子22jkS下是不变的，由于22222222222()2(())(22)JjJJjJjkJjJjkQQSSZZZZZZ其中，Q=diag（2,1）。因此，对于式（6）中22jkfS的表示我们有如下引理。引理1保留本部分的符号和定义。令22j表示以22j为因子的一维上采样算子，*1表示沿水平方向的一维卷积算子，21()jhn是三角多项式的傅里叶系数21221121101()()jkinjnkHhneZ（7）可得422112222()22,2JjJjJjJkkknfSxfSnxnxnZ其中，2122()jJJjfnfhn此引理的证明需要以下结论，它来自小波理论的级联算法命题1假定2LR和2LR分别满足等式(3)和(4)，对正整数12jj，有221121121111112112(2)(2)2(2)jjjjjjjjdxnhdnxdZ（8）和2211211211111112112(2)(2)2(2)jjjjjjjjdxngdnxdZ（9）其中，jh和jg分别是三角多项式jH和jG的傅里叶系数，jH的定义如式（7）所示。对固定的j0，jG的定义为2122221111111011()()()jkjininjnnkGhnegneZZ引理1的证明：令12,2jJjJj，将其带入式（8），有2224211121111112(2)(2)2(2)JJjJjJjJjdxnhdnxd（10）由于是一个二维可分离函数，即121112,xxxx，因此有221211112221,2222JJJJJnnfxfnnxnxnZZ由式（10）可得422()22JjJjJnfxfnQxn其中，Q=diag（2,1）。使用2222jjjkkQSSQ，22jkfS最终可表示为4222222422422()22()22()2(2)JjJjjJjkknJjJjJkknJjJjJknfSxfnQSxnfnSQxSnfnSQxn证明完毕。式（6）的第二步数字化是剪切波本身的离散化，由命题1可得到如下的结论。引理2保留此部分的符号和定义。24,,112222()(2)(2)2(2)JjJjJjJjkmJjJjdxgdmhdmxd如前所述，充分应用与各向异性抽样矩阵2j相关联的离散可分离小波变换，对与12,0jj，2clZ，定义线性变换,12cjjW212,121122121212122,(2)(2),,,jjjjjjmWcnngmnhmncmmnnZZ（11）引理1和2共同完成了剪切波系数,,,jkmf的离散化算术实现。因此，有如下定理：定理1保留此部分的符号和定义。令22j表示以2j/2为因子的一维上采样算子，*1表示沿水平方向的一维卷积算子，剪切波系数,,,jkmf可化为,,,21222,()jkmJjJjJkkjjfWfShm其中22121,,kkjjnSnnhnhnZ图1（a）显示了剪切波变换的步骤。使用定理1计算剪切波系数时，限制与抽样矩阵2j相关的可分离小波变换的尺度系数为22212222:()djJJkkjJjkSfnfShnflZ（12）在详细描述实现步骤之前，先进一步研究尺度系数22djJkSf。22djJkSf可以看做是通过数字剪切操作22djkS在整数格2Z上对Jf的采样。图1（b）给出了2214jk时22djkS的基本过程。图1（a）计算剪切波系数的步骤：沿水平轴细化（上行），与剪切矩阵相关的重采样（中间）和可分离小波变换（下行）；（b）4j，1k时的水平方向细化过程事实上，对于任意剪切系数k，式（12）中的滤波器系数()kn都可以很容易预先计算得到。在实际计算中经常假设(0,0)k，有时甚至可以跳过这一卷积步骤。离散可分离剪切波变换（DSST）的计算方法可通过如下步骤表示：Step1：在精细尺度jJ以2j/2为因子对其给定的数据Jf一维上采样。Step2：在精细尺度jJ，计算上采样后的数据Jf和一维低通滤波器2jh的一维卷积，得到Jf。Step3：在精细尺度jJ，根据剪切抽样矩阵kS重采样Jf得到(())JkfSn。由于整数格在剪切矩阵kS下是不变的，因此重采样的步骤也很简单。Step4：在精细尺度jJ，以2j/2为因子对2jh一维下采样后与(())JkfSn进行一维卷积。Step5：应用可分离小波变换,2JjJjW遍历尺度0,1,,1jJ。2、冗余度分析实用性要求的主要问题之一就是可控的冗余。为了能够定量的分析冗余离散剪切波变换的冗余度，假设输入数据f是一个由二维尺度函数转换的有限的线性组合，在尺度J表示如下：21210012()(2)JJJnnnfxdxn上式满足式（5）的假设。为了使结果更具普遍性，在变换中使用任意的抽样矩阵12(,)cMdiagcc，剪切元素的形式如下所示34,,2()2()jjkmkjcSMm那么可以得到如下结论：命题2离散可分离剪切波变换（DSST）的冗余度为12413cc证明：首先考虑在固定尺度{0,.1}jJ水平域的剪切元素，观查可知，剪切指数k有212j个，与尺度矩阵2j和抽样矩阵cM相关的变换指数有211222()jjcc个。因此，在水平域表示f需要211122()jcc个剪切元素。同理，在垂直域也需要相同个数的剪切元素。最后，在最粗糙尺度0j尺度函数需要21c个变换。遍历所有尺度所需必要剪切元素的个数为212012124422213JJjjcccc冗余度为此数据与原始系数个数的比值，J时得证。3、计算复杂度命题3离散可分离剪切波变换的计算复杂度为log122122LOLN证明：由离散实现的步骤可以看出，最耗时间的是步骤1-步骤4在最精细尺度jJ对尺度系数的计算，这些步骤要求一维上采样后，在与剪切参数k相关的每个方向上进行一维卷积。令L表示最精细尺度jJ的方向数目，22(221)jL，N表示2D输入数据的大小，在1-4步中尺度系数的计算复杂度为2(2)jOLN。步骤5中与2j相关的可分离小波变换需要()ON次操作，因此可忽略不计。