V-系统的快速变换算法

doi:10.3785/j.issn.1008-9497.2023.06.011

V-系统的快速变换算法

陈伟^,^,¹, 戚谨雯¹, 李坚², 宋瑞霞³

1.江南大学人工智能与计算机学院，江苏无锡 214122

2.澳门理工大学应用科学学院，澳门 999078

3.北方工业大学理学院，北京 100144

A fast algorithm for V-system

CHEN Wei^,^,¹, QI Jinwen¹, LI Jian², SONG Ruixia³

1.School of Artificial Intelligence and Computer Science，Jiangnan University，Wuxi 214122，Jiangsu Province，China

2.Faculty of Applied Sciences，Macao Polytechnic University，Macao 999078，China

3.College of Sciences，North China University of Technology，Beijing 100144，China

收稿日期: 2023-06-21 修回日期: 2023-07-17 接受日期: 2023-07-24

Received: 2023-06-21 Revised: 2023-07-17 Accepted: 2023-07-24

作者简介 About authors

陈伟（1986—），ORDID：https//orcid.org/0009-0002-2728-494X，男，博士，副教授，主要从事计算机图形学研究，E-mail：chenwei.must@gmail.com. , E-mail：chenwei.must@gmail.com

摘要

V-系统是 $L^{2} [0,1]$ 上的一类完备正交分段多项式函数系，由于其基函数的间断特性，在非连续信号的表达与分析上优势显著。然而，在目前的V-系统变换算法中，对于一个长度为N的信号，不仅需要事先生成并存储一个N阶的正交矩阵，而且其时间复杂度高达 $Ο (N^{3})$ 。为实现对大规模数据的高效处理，从V-系统的多分辨率分析角度出发，设计并实现了V-系统的快速分解与重构算法，不仅无须存储额外信息，而且其时间复杂度仅为 $Ο (N)$ 。测试结果表明，提出的快速算法能够满足大规模数据高效处理要求，为V-系统在更多领域的应用奠定了基础。

关键词： V-系统 ; 多分辨率分析 ; 双尺度方程 ; 多小波 ; 快速算法

Abstract

V-system is a kind of complete orthogonal piecewise polynomial function system on $L^{2} [0,1]$ , because of the discontinuous nature of its basis functions, it has significant advantages in the expression and analysis of discontinuous signals. However, in the current V-system transformation algorithm, for a signal with a length of N, it not only needs to generate and store an N-order orthogonal matrix in advance, but also its time complexity is as high as $Ο (N^{3})$ . Therefore, in order to adapt to the efficient processing needs, this paper designs and implements a fast decomposition and reconstruction algorithm for V-systems from the perspective of multi-resolution analysis of V-systems. This fast algorithm does not need to store additional information, and its time complexity is only $Ο (N^{2})$ . The test results show that the fast algorithm proposed in this paper can meet the requirements of high-efficiency processing of large-scale data, which lays the foundation for the application of V-system in more fields.

Keywords： V-system ; orthogonal ; resolution analysis ; double scale equation ; multi wavelet ; fast algorithm

PDF (1706KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

陈伟, 戚谨雯, 李坚, 宋瑞霞. V-系统的快速变换算法. 浙江大学学报(理学版)[J], 2023, 50(6): 761-769 doi:10.3785/j.issn.1008-9497.2023.06.011

CHEN Wei, QI Jinwen, LI Jian, SONG Ruixia. A fast algorithm for V-system. Journal of Zhejiang University(Science Edition)[J], 2023, 50(6): 761-769 doi:10.3785/j.issn.1008-9497.2023.06.011

正交变换为信号提供了一种有用的表示方式，通过将信号映射至由正交函数支撑的空间，获得信号的频谱，在信号处理中具有广泛应用。经典的傅里叶变换建立在三角函数之上，已形成一套完整的频率分析理论与方法。为改进傅里叶变换不能分析信号局部性质的不足，自20世纪80年代以来，小波变换应运而生，其数学基础为各类具有时频局部性的正交小波基函数。快速变换是实现高效信号处理的关键技术，虽然傅里叶分析与小波分析理论早已成熟，但直到快速傅里叶变换和快速小波变换算法的提出，才使得这两种数学理论走向实际工程应用，实现了信号处理的革命性飞跃^［1-2］。随着现代信号处理理论与技术的不断深化，并向不同应用领域极速拓展，正交变换已成为信号处理的研究热点^［3-5］。

近年来，国内学者提出了一类新的完备正交函数系——V-系统^［6］。与传统的只包含连续或光滑基函数的正交变换（诸如三角函数、各类正交多项式以及各类连续小波等）不同，V-系统是一类非连续正交函数系^［7］，也就是说，V-系统中同时包含了连续、光滑以及间断的各类基函数，这一特性使其在实际信号处理中具有独到优势，因为实际信号往往具有复杂的形态，既包含连续光滑的部分，也存在大量不同层次的间断，而V-系统能够实现信号的全局高效逼近，在几何模型表达^［8-9］、形状检索^［10-11］、图像处理^［12-14］等领域得到了广泛应用。

然而，由于V-系统还没有相应的快速变换算法，导致其在实际应用中产生高昂的空间与时间复杂度代价。假设实际信号以一个N维向量表示，为实现相应的V-系统变换，先选取前N个V-系统基函数，对每个基函数采样N个离散点，形成N×N阶采样矩阵。再对该采样矩阵进行正交化处理，得到相应的V-系统正交矩阵。首先，不同于传统的三角函数或多项式函数具有统一的解析表达式，V-系统基函数呈分段表达形式，导致其采样矩阵的获得非常复杂，其次，对采样矩阵进行正交化处理需要 $N^{3}$ 次乘法运算，最后，通过正交矩阵进行信号变换及反变换也各需 $N^{2}$ 次乘法运算。因此V-系统变换的时间复杂度达 $Ο (N^{3})$ ，时间复杂度和空间复杂度均很高。为减少计算代价，目前采取的策略通常是事先生成并保存若干固定阶数的V-系统正交矩阵（如N=16，32，64，…），然后根据信号实际长度选择相应的正交矩阵。当信号长度N较大时，正交矩阵的存储将不可避免地遇到瓶颈，从而无法实现相应的V-系统变换。

为真正发挥V-系统的独特性质，将其应用于大规模数据场景，设计并实现V-系统的快速变换算法是一项必不可少的基础性工作。此前，文献［15-16］分别构造了与V-系统等价、函数结构更加简单的W-系统和广义V-系统两类正交函数系，在此基础上借助快速Walsh变换思想实现了这两类正交函数的快速变换。然而，这两类正交函数毕竟不是V-系统，而且也没有研究它们与V-系统的转换关系。因此，V-系统的快速变换仍未实现。

本文的目的是实现直接基于V-系统的快速变换。实际上，V-系统不仅是一类正交分段多项式函数系，文献［17］从理论上也证明了V-系统是一类多小波，因此，本文的思路是从小波的角度看待V-系统。首先给出V-系统的多分辨率分析；然后给出V-系统的双尺度方程；在此基础上，得到V-系统的快速分解与重构算法，亦称V-系统变换的Mallat算法。与传统的V-系统变换相比，本文提出的快速算法只需存储4个k+1阶滤波器系数矩阵（k为V-系统的阶数，通常k=1，2，3），而且其时间复杂度也大幅降为 $Ο (N)$ 。

1　V-系统

1.1　V-系统的传统构造方法

V-系统（全称为k次V-系统）是一类定义在区间［0，1］上的完备正交分段多项式函数系。按照“Legendre多项式、生成元函数及压缩-平移算子”的思路构造V-系统。V-系统具有明晰的函数组织结构。

首先，V-系统包含区间［0，1］的前k+1个归一化Legendre多项式，记为

$φ_{k}^{0} (x), φ_{k}^{1} (x), \dots, φ_{k}^{k} (x), x \in [0,1]$ ；

其次，对V-系统其余部分，为清晰表达每个基函数在V-系统中的分层、分组及分类的排列次序，将基函数记为 $ψ_{k, n}^{j, i} (x)$ ，表示k次V-系统第n层、第j组的第i类基函数。当n=0时，该层也包含k+1个基函数，这些基函数是根据正交性、对称性以及连续性条件确定的。由于该层基函数是生成V-系统其他层基函数的关键，故称其为生成元。构造生成元的方法不同^{［6，18-19］}，但结果相同，记为

ψ_{k, 0}^{0,0} (x), ψ_{k, 0}^{0,1} (x), \dots, ψ_{k, 0}^{0, k} (x), x \in [0,1] ，

每个生成元函数均为区间［0，1］以x=0.5为节点分段k次的多项式，而且第i个生成元 $ψ_{k, 0}^{i} (x)$ （i=0，1，…，k）在x=0.5处的光滑性为 $C^{k - 1 - i}$ ，也就是说，这些生成元函数包含了从函数间断到函数各阶导数间断的各种层次间断情形。

接下来，从第n=1层开始，通过将第n=0层中的每个生成元函数 $ψ_{k, 0}^{i} (x)$ （i=0，1，…，k）压缩 $2^{n}$ 倍，然后分别复制至该层的每个等分子区间，得到第n层的所有基函数［共计（k+1） $2^{n}$ 个］，表达式为

ψ_{k, n}^{j, i} (x) = \{\begin{array}{l} \sqrt[]{2^{n}} ψ_{k, 0}^{0, i} (2^{n} x - j), x \in (\frac{j}{2^{n}}, \frac{j + 1}{2^{n}}), \\ 0, 其他, \end{array}

\begin{matrix}  \end{matrix}

（1）

i=0，1，…，k；j=0，1，3，…， $2^{n} - 1$ ；n=0，1，2，…。

可以证明，按照上述构造方法得到的V-系统具有正交性及完备性。表1为k=0，1，2，3次V-系统的函数图形。与其他类型的正交函数系（三角函数系、各类正交多项式及各类连续小波等）相比，V-系统的显著特征在于其丰富的间断性，这一特征在连续与间断并存的复杂信号处理中具有明显优势。

表1 在区间［0， 1］的k次完备正交V-系统

Table 1 Complete k th-order orthogonal V-system on the interval ［0， 1］

$k$	$V$ 系统
注释	尺度空间 $V_{0}$ $\begin{array}{l} ϕ_{k}^{0} (x), \\ ϕ_{k}^{1} (x), \\ \dots, \\ ϕ_{k}^{k} (x) \end{array}$	小波空间 $W_{0}$ $\begin{array}{l} ψ_{k, 0}^{0,0} (x), \\ ψ_{k, 0}^{0,1} (x), \\ \dots, \\ ψ_{k, 0}^{0, k} (x) \end{array}$	小波空间 $W_{1}$ $ψ_{k, 1}^{j, i} (x) = \{\begin{array}{l} \begin{matrix} \sqrt[]{2} ψ_{k, 0}^{0, i} (2 x - j), \\ x \in (\frac{j}{2}, \frac{j + 1}{2}), \end{matrix} \\ 0, 其他, \end{array}$ $\begin{array}{l} i = 0,1, 2, \dots, k; \\ j = 0,1 \end{array}$	小波空间 $W_{2}$ $ψ_{k, 2}^{j, i} (x) = \{\begin{array}{l} \begin{matrix} \sqrt[]{2} ψ_{k, 0}^{0, i} (4 x - j), \\ x \in (\frac{j}{4}, \frac{j + 1}{4}), \end{matrix} \\ 0, 其他, \end{array}$ $\begin{array}{l} i = 0,1, 2 ， \dots, k; \\ j = 0,1, 2,3 \end{array}$	小波空间 $W_{n}$ $\begin{array}{l} ψ_{k, n}^{j, i} (x) = \\ \{\begin{array}{l} \begin{array}{l} \sqrt[]{2} ψ_{k, 0}^{0, i} (2^{n} x - j), \\ x \in (\frac{j}{2^{n}}, \frac{j + 1}{2^{n}}), \end{array} \\ 0, 其他, \end{array} \end{array}$ $\begin{array}{l} i = 0,1, 2 ， \dots, k; \\ j = 0,1, 3 ， \dots, 2^{n} - 1 \end{array}$
0					…
1					…
2					…
3					…

新窗口打开| 下载CSV

1.2　基于采样矩阵的V-系统变换

为实现离散信号的V-系统变换与重构，须用到有限V变换，已有方法是预先构造离散V-系统正交矩阵。假设信号长度 $N = (k + 1) 2^{n}$ ，选取k次V-系统的前n层基函数，分别按分层、分组及分类的次序排列，记为 $V_{i} (x) (i = 1,2, \dots, N)$ 。将区间［0，1］等分为N个子区间，在每个子区间上对这N个基函数逐个积分，得到N×N的采样矩阵 A，其中，

A_{i j} = \int_{\frac{j - 1}{N}}^{\frac{j}{N}} V_{i} (x) d x, i, j = 1,2, \dots, N

。（2）

通常此时的 $A_{i j}$ 并不是正交矩阵，需要进行正交化处理得到相应的正交矩阵 V。为得到离散V-系统的正交矩阵，不仅需要对各个基函数做大量积分运算，还需要对采样矩阵进行Gram-Schmidt正交化运算，计算量很大，而且数值稳定性较差。在实际应用中，一般先计算并存储若干固定阶数的正交 V 矩阵（如N=16，32，64，…），再根据信号的实际长度选择相应的矩阵，此方法只适合小规模数据量的信号处理场合。当信号长度N较大时，正交矩阵的存储将不可避免地遇到瓶颈。

假设信号 $f = (f_{1}, f_{2}, \dots, f_{N})^{T}$ ，那么基于N阶正交矩阵 V，可通过下式直接进行正交V变换：

λ = V \cdot f

，（3）

其中， $λ = （ λ_{1}, λ_{2}, \dots, λ_{N})^{T}$ 为原信号 $f$ 在k次V-系统下的变换系数，常称为V谱。假设根据实际信号处理要求，V谱 $λ$ 经处理后变为 $λ^{'}$ 。由于变换矩阵是正交的，因此相应的重构信号（逆变换）可由

f^{'} = V^{T} \cdot λ^{'}

（4）

直接得到。可以看出，无论是信号分解（正变换）还是重构（逆变换），不仅需要事先生成及存储N阶矩阵，而且在具体变换时也需要做 $N^{2}$ 次乘法运算。可以看出，基于正交矩阵的V-系统变换算法的复杂度很高，阻碍了其在实际大规模信号处理中的应用。因此，设计及实现V-系统的快速变换算法是一项重要的工作。

2　V系统快速变换算法

2.1　V-系统的多分辨性分析

从V-系统的传统构造方法中可以看出，虽然 V-系统基函数无整体解析表达式，但函数系却呈现十分清晰明了的层次结构。实际上，V-系统的这种层次关系，可从理论上证明其就是在区间［0，1］上的多小波^［17］。因此，基于小波变换的思想，从多分辨率分析（MRA）的角度重新定义V-系统，可得到V-系统快速变换算法。

令 $V_{0} = \bar{s p a n} {φ_{k}^{i} (x), i = 0,1, 2 ， \dots, k}$ ， $W_{0} = \bar{s p a n} {ψ_{k, 0}^{0, i} (x), i = 0,1, 2 ， \dots, k}$ ，则

d i m V_{0} = k + 1, d i m W_{0} = k + 1

，

且 ${φ_{k}^{i} (x), i = 0,1, 2 ， \dots, k}$ 和 ${ψ_{k, 0}^{0, i} (x), i = 0,1,$ $2 ， \dots, k}$ 分别构成 $V_{0}$ 和 $W_{0}$ 的标准正交基。再记

W_{1} = \bar{s p a n} {ψ_{k, 1}^{j, i} (x), i = 0,1, 3 ， \dots, k; j = 0,1}

，

则 $d i m W_{1} = 2 (k + 1)$ ，且 ${ψ_{k, 1}^{j, i} (x), i = 0,1, 2 ， \dots, k;$ $j = 0,1}$ 构成 $W_{1}$ 的正交基。

通常记

\begin{array}{l} W_{n - 1} = \bar{s p a n} {ψ_{k, n - 1}^{j, i} (x), i = 0,1, 3 ， \dots, k; \\ j = 0,1, 3 ， \dots, 2^{n - 1} - 1} \end{array}

，

则 $d i m W_{n - 1} = 2^{n - 1} (k + 1)$ ，且 ${V_{k, n - 1}^{i, j} (x), i = 0,1, 2 ， \dots,$ $k; j = 0,1, 3 ， \dots, 2^{n - 1} - 1}$ 就是 $W_{n - 1}$ 的正交基。

令 $V_{n} = V_{n - 1} \oplus W_{n - 1}$ ，则 $V_{0} \subset V_{1} \subset V_{2} \subset \dots$ ，且 $\underset{n \in Z}{\cap} V_{n} = {0}$ ， $L^{2} [0,1] = \bar{\underset{n \in Z}{\cup} V_{n}}$ ，也就是说V-系统在 $L^{2} [0,1]$ 形成k+1重的正交多分辨率分析。其中，排在V-系统最前面的k+1个Legendre多项式 ${φ_{k}^{i} (x), i = 0,1, 2 ， \dots, k}$ 即为尺度函数，而V-系统的生成元函数 ${ψ_{k, 0}^{i} (x), i = 0,1, 2 ， \dots, k}$ 即为小波函数，第n（n≥1）层基函数为相应正交补空间 $W_{n}$ 的正交基。

基于V-系统的多分辨率分析性质，可得V-系统的矩阵双尺度方程。将k次V-系统的尺度函数和小波函数记为向量形式，分别为

Φ_{k} (x) = [φ_{k}^{0} (x), φ_{k}^{1} (x), \dots, φ_{k}^{k} {(x)]}^{T}

，（5）

Ψ_{k} (x) = [ψ_{k ， 0}^{0} (x), ψ_{k ， 0}^{1} (x), \dots, ψ_{k ， 0}^{k} {(x)]}^{T}

，（6）

满足矩阵双尺度方程：

Φ_{k} (x) = C_{0} Φ_{k} (2 x) + C_{1} Φ_{k} (2 x - 1)

，（7）

Ψ_{k} (x) = D_{0} Φ_{k} (2 x) + D_{1} Φ_{k} (2 x - 1)

，（8）

其中， $C_{0}$ ， $C_{1}$ ， $D_{0}$ ， $D_{1}$ 为k+1阶矩阵，称为k次V-系统的双尺度方程系数矩阵。

在传统小波分析理论中，多分辨率分析在于给出一种构造小波的途径，通过在MRA下求解双尺度方程得到相应的尺度函数和小波函数，但通常并不能得到解析解，这是传统小波的不足之处之一。而V-系统并不是通过MRA构造的，具有明确且简洁的表达式。这里给出V-系统的MRA，目的是得到各层子空间之间的具体关系，用于推导V-系统分解与重构的级联关系。

由于 $Φ_{k} (2 x) ⋃ Φ_{k} (2 x - 1)$ 为在空间 $V_{1}$ 中的正交基，因此易计算得到k次V-系统的双尺度方程系数矩阵，其中，

C_{0} (i, j) = 2 \int_{0}^{\frac{1}{2}} φ_{k}^{i - 1} (x) φ_{k}^{j - 1} (2 x) d x

，（9）

C_{1} (i, j) = 2 \int_{\frac{1}{2}}^{1} φ_{k}^{i - 1} (x) φ_{k}^{j - 1} (2 x - 1) d x

，（10）

D_{0} (i, j) = 2 \int_{0}^{\frac{1}{2}} ψ_{k, 0}^{i - 1} (x) φ_{k}^{j - 1} (2 x) d x

，（11）

D_{1} (i, j) = 2 \int_{\frac{1}{2}}^{1} ψ_{k, 0}^{i - 1} (x) φ_{k}^{j - 1} (2 x - 1) d x

，（12）

i, j = 1,2, \dots, k + 1

。

在实际应用中最常用的双尺度方程系数矩阵有：

当k=1时，有

\begin{array}{l} C_{0} = [\begin{matrix} 1 & 0 \\ \frac{\sqrt[]{3}}{2} & \frac{1}{2} \end{matrix}], C_{1} = [\begin{matrix} 1 & 0 \\ - \frac{\sqrt[]{3}}{2} & \frac{1}{2} \end{matrix}], \\ D_{0} = [\begin{matrix} 0 & 1 \\ - \frac{1}{2} & \frac{\sqrt[]{3}}{2} \end{matrix}], D_{1} = [\begin{matrix} 0 & - 1 \\ \frac{1}{2} & \frac{\sqrt[]{3}}{2} \end{matrix}]; \end{array}

当k=2时，有

\begin{array}{l} C_{0} = [\begin{matrix} 1 & 0 & 0 \\ \frac{\sqrt[]{3}}{2} & \frac{1}{2} & 0 \\ 0 & \frac{\sqrt[]{15}}{4} & \frac{1}{4} \end{matrix}], C_{1} = [\begin{matrix} 1 & 0 & 0 \\ - \frac{\sqrt[]{3}}{2} & \frac{1}{2} & 0 \\ 0 & - \frac{\sqrt[]{15}}{4} & \frac{1}{4} \end{matrix}], \\ D_{0} = [\begin{matrix} - \frac{\sqrt[]{5}}{6} & \frac{\sqrt[]{15}}{6} & \frac{2}{3} \\ 0 & - \frac{1}{4} & \frac{\sqrt[]{15}}{4} \\ \frac{1}{3} & - \frac{\sqrt[]{3}}{3} & \frac{\sqrt[]{5}}{3} \end{matrix}], D_{1} = [\begin{matrix} \frac{\sqrt[]{5}}{6} & \frac{\sqrt[]{15}}{6} & - \frac{2}{3} \\ 0 & \frac{1}{4} & \frac{\sqrt[]{15}}{4} \\ - \frac{1}{3} & - \frac{\sqrt[]{3}}{3} & - \frac{\sqrt[]{5}}{3} \end{matrix}] ； \end{array}

当k=3时，有

\begin{array}{l} C_{0} = [\begin{matrix} 1 & 0 & 0 & 0 \\ \frac{\sqrt[]{3}}{2} & \frac{1}{2} & 0 & 0 \\ 0 & \frac{\sqrt[]{15}}{4} & \frac{1}{4} & 0 \\ - \frac{\sqrt[]{7}}{8} & \frac{\sqrt[]{21}}{8} & \frac{\sqrt[]{35}}{8} & \frac{1}{8} \end{matrix}], \\ C_{1} = [\begin{matrix} 1 & 0 & 0 & 0 \\ - \frac{\sqrt[]{3}}{2} & \frac{1}{2} & 0 & 0 \\ 0 & - \frac{\sqrt[]{15}}{4} & \frac{1}{4} & 0 \\ \frac{\sqrt[]{7}}{8} & \frac{\sqrt[]{21}}{8} & - \frac{\sqrt[]{35}}{8} & \frac{1}{8} \end{matrix}], \end{array}

\begin{array}{l} D_{0} = [\begin{matrix} 0 & - \frac{\sqrt[]{21}}{20} & \frac{3 \sqrt[]{35}}{20} & \frac{2}{5} \\ \frac{\sqrt[]{5}}{8} & - \frac{\sqrt[]{15}}{8} & \frac{3}{8} & \frac{\sqrt[]{35}}{8} \\ 0 & \frac{1}{10} & - \frac{\sqrt[]{15}}{10} & \frac{\sqrt[]{21}}{5} \\ - \frac{1}{4} & \frac{\sqrt[]{3}}{4} & - \frac{\sqrt[]{5}}{4} & \frac{\sqrt[]{7}}{4} \end{matrix}], \\ D_{1} = [\begin{matrix} 0 & \frac{\sqrt[]{21}}{20} & \frac{3 \sqrt[]{35}}{20} & - \frac{2}{5} \\ - \frac{\sqrt[]{5}}{8} & - \frac{\sqrt[]{15}}{8} & - \frac{3}{8} & \frac{\sqrt[]{35}}{8} \\ 0 & - \frac{1}{10} & - \frac{\sqrt[]{15}}{10} & - \frac{\sqrt[]{21}}{5} \\ \frac{1}{4} & \frac{\sqrt[]{3}}{4} & \frac{\sqrt[]{5}}{4} & \frac{\sqrt[]{7}}{4} \end{matrix}] \end{array}

。

2.2　V-系统的快速分解与重构算法

有了矩阵双尺度方程，便可实现信号在V-系统的分解与重构。

设 $f (x) \in V_{n}$ ，若记

Φ_{k, n}^{j} (x) = \sqrt[]{2^{n}} Φ_{k} (2^{n} x - j) = \sqrt[]{2^{n}} {[φ_{k}^{0} (2^{n} x - j), φ_{k}^{1} (2^{n} x - j), \dots, φ_{k}^{k} (2^{n} x - j)]}^{T} ，

x \in (\frac{j}{2^{n}}, \frac{j + 1}{2^{n}}), j = 0,1, 3, \dots, 2^{n} - 1

，（13）

则

f (x) = \sum_{j = 0}^{2^{n} - 1} c_{n, j}^{T} Φ_{k, n}^{j} (x)

，（14）

其中， $c_{n, j} = [c_{n, j}^{0}, c_{n, j}^{1}, \dots, c_{n, j}^{k}]^{T}$ 表示第j个系数向量。由于 $\{\cup_{j = 0}^{2^{n} - 1} Φ_{k, n}^{j} (x)\}$ 为 $V_{n}$ 的一组标准正交基，故有

c_{n, j} = 〈f (x), Φ_{k, n}^{j} (x)〉 = \sqrt[]{2^{n}} [〈f (x), φ_{k}^{0} (2^{n} x - j)〉, 〈f (x), φ_{k}^{1} (2^{n} x - j)〉, \dots, 〈f (x), φ_{k}^{k} (2^{n} x - j)〉],

（15）

其中，

\begin{array}{l} 〈f (x), φ_{k}^{i} (2^{n} x - j)〉 = f (x) φ_{k}^{i} (2^{n} x - j) d x, \\ i = 0,1, 2, \dots, k \end{array}

。

又由于 $V_{n} = V_{n - 1} \oplus W_{n - 1}$ ，记

Ψ_{k, n}^{j} (x) = [ψ_{k, n}^{j, 0} (x), ψ_{k, n}^{j, 1} (x), \dots, ψ_{k, n}^{j, k} {(x)]}^{T}

为V-系统第n层第j组由k+1个基函数组成的向量。所以 $\cup_{j = 0}^{2^{n - 1} - 1} \{Φ_{k, n - 1}^{j} (x) ⋃ Ψ_{k, n - 1}^{j} (x)\}$ 也是 $V_{n}$ 中的一组标准正交基，故有

\begin{array}{l} f (x) = \sum_{j = 0}^{2^{n - 1} - 1} c_{n - 1, j}^{T} Φ_{k, n - 1}^{j} (x) + \\ \sum_{j = 0}^{2^{n - 1} - 1} d_{n - 1, j}^{T} Ψ_{k, n - 1}^{j} (x) \end{array}

，（16）

其中， $d_{n - 1, j} = {[d_{n - 1, j}^{0}, d_{n - 1, j}^{1}, \dots, d_{n - 1, j}^{k}]}^{T}$ 。

下求式（16）的系数向量 $c_{n - 1, j}$ 和 $d_{n - 1, j}$ 。

\begin{array}{l} c_{n - 1, j} = 〈f (x), Φ_{k, n - 1}^{j} (x)〉 = \\ 〈c_{n, 2 j}^{T} Φ_{k, n}^{2 j} (x), Φ_{k, n - 1}^{j} (x)〉 + \\ 〈c_{n, 2 j + 1}^{T} Φ_{k, n}^{2 j + 1} (x), Φ_{k, n - 1}^{j} (x)〉 = \\ \frac{1}{\sqrt[]{2}} 〈c_{n, 2 j}^{T} Φ_{k, n}^{2 j} (x), C_{0} Φ_{k, n}^{2 j} (x) + C_{1} Φ_{k, n}^{2 j + 1} (x)〉 + \\ \frac{1}{\sqrt[]{2}} 〈c_{n, 2 j + 1}^{T} Φ_{k, n}^{2 j + 1} (x), C_{0} Φ_{k, n}^{2 j} (x) + C_{1} Φ_{k, n}^{2 j + 1} (x)〉 = \\ \frac{1}{\sqrt[]{2}} 〈c_{n, 2 j}^{T} Φ_{k, n}^{2 j} (x), C_{0} Φ_{k, n}^{2 j} (x)〉 + \\ \frac{1}{\sqrt[]{2}} 〈c_{n, 2 j + 1}^{T} Φ_{k, n}^{2 j + 1} (x), C_{1} Φ_{k, n}^{2 j + 1} (x)〉 = \\ \frac{1}{\sqrt[]{2}} (C_{0} c_{n, 2 j} + C_{1} c_{n, 2 j + 1}) ； \end{array}

（17）

\begin{array}{l} d_{n - 1, j} = 〈f (x), Ψ_{k, n - 1}^{j} (x)〉 = \\ 〈c_{n, 2 j}^{T} Φ_{k, n}^{2 j} (x), Ψ_{k, n - 1}^{j} (x)〉 + \\ 〈c_{n, 2 j + 1}^{T} Φ_{k, n}^{2 j + 1} (x), Ψ_{k, n - 1}^{j} (x)〉 = \\ \frac{1}{\sqrt[]{2}} 〈c_{n, 2 j}^{T} Φ_{k, n}^{2 j} (x), D_{0} Φ_{k, n}^{2 j} (x) + D_{1} Φ_{k, n}^{2 j + 1} (x)〉 + \\ \frac{1}{\sqrt[]{2}} 〈c_{n, 2 j + 1}^{T} Φ_{k, n}^{2 j + 1} (x), D_{0} Φ_{k, n}^{2 j} (x) + D_{1} Φ_{k, n}^{2 j + 1} (x)〉 = \\ \frac{1}{\sqrt[]{2}} 〈c_{n, 2 j}^{T} Φ_{k, n}^{2 j} (x), D_{0} Φ_{k, n}^{2 j} (x)〉 + \\ \frac{1}{\sqrt[]{2}} 〈c_{n, 2 j + 1}^{T} Φ_{k, n}^{2 j + 1} (x), D_{1} Φ_{k, n}^{2 j + 1} (x)〉 = \\ \frac{1}{\sqrt[]{2}} (D_{0} c_{n, 2 j} + D_{1} c_{n, 2 j + 1}) 。 \end{array}

（18）

式（17）和式（18）分别给出了系数向量 $c_{n, j}$ 与 $c_{n - 1, j}$ ，及 $c_{n, j}$ 与 $d_{n - 1, j}$ 之间的关系，该关系就是V-系统的快速分解算法。

下面考虑重构过程，即由式（16）求式（14），

\begin{array}{l} f (x) = \sum_{j = 0}^{2^{n - 1} - 1} c_{n - 1, j}^{T} Φ_{k, n - 1}^{j} (x) + \\ \sum_{j = 0}^{2^{n - 1} - 1} d_{n - 1, j}^{T} Ψ_{k, n - 1}^{j} (x) = \\ \frac{1}{\sqrt[]{2}} \sum_{j = 0}^{2^{n - 1} - 1} c_{n - 1, j}^{T} [C_{0} Φ_{k, n}^{2 j} (x) + C_{1} Φ_{k, n}^{2 j + 1} (x)] + \\ \frac{1}{\sqrt[]{2}} \sum_{j = 0}^{2^{n - 1} - 1} d_{n - 1, j}^{T} [C_{0} Φ_{k, n}^{2 j} (x) + C_{1} Φ_{k, n}^{2 j + 1} (x)], \end{array}

（19）

对上式两端分别与 $Φ_{k, n}^{2 j} (x)$ ， $Φ_{k, n}^{2 j + 1} (x)$ 作内积，得：

\begin{array}{l} c_{n, 2 j} = 〈f (x), Φ_{k, n}^{2 j} (x)〉 = \\ \frac{1}{\sqrt[]{2}} 〈c_{n - 1, j}^{T} \cdot C_{0} \cdot Φ_{k, n}^{2 j} (x), Φ_{k, n}^{2 j} (x)〉 + \\ \frac{1}{\sqrt[]{2}} 〈d_{n - 1, j}^{T} \cdot D_{0} \cdot Φ_{k, n}^{2 j} (x), Φ_{k, n}^{2 j} (x)〉 = \\ \frac{1}{\sqrt[]{2}} (C_{0}^{T} \cdot c_{n - 1, j} + D_{0}^{T} \cdot d_{n - 1, j}); \end{array}

（20）

\begin{array}{l} c_{n, 2 j + 1} = 〈f (x), Φ_{k, n}^{2 j + 1} (x)〉 = \\ \frac{1}{\sqrt[]{2}} 〈c_{n - 1, j}^{T} \cdot C_{1} \cdot Φ_{k, n}^{2 j + 1} (x), Φ_{k, n}^{2 j + 1} (x)〉 + \\ \frac{1}{\sqrt[]{2}} 〈d_{n - 1, j}^{T} \cdot D_{1} \cdot Φ_{k, n}^{2 j + 1} (x), Φ_{k, n}^{2 j + 1} (x)〉 = \\ \frac{1}{\sqrt[]{2}} (C_{1}^{T} \cdot c_{n - 1, j} + D_{1}^{T} \cdot d_{n - 1, j}) 。 \end{array}

（21）

综上，可得V-系统的分解及重构公式。其中，分解公式为

\{\begin{matrix} c_{n - 1, j} = \frac{1}{\sqrt[]{2}} (C_{0} \cdot c_{n, 2 j} + C_{1} \cdot c_{n, 2 j + 1}) ， \\ d_{n - 1, j} = \frac{1}{\sqrt[]{2}} (D_{0} \cdot c_{n, 2 j} + D_{1} \cdot c_{n, 2 j + 1}) ； \end{matrix}

（22）

重构公式为

\{\begin{array}{l} c_{n, 2 j} = \frac{1}{\sqrt[]{2}} (C_{0}^{T} \cdot c_{n - 1, j} + D_{0}^{T} \cdot d_{n - 1, j}), \\ c_{n, 2 j + 1} = \frac{1}{\sqrt[]{2}} (C_{1}^{T} \cdot c_{n - 1, j} + D_{1}^{T} \cdot d_{n - 1, j}), \end{array}

（23）

j = 0,1, \dots, 2^{n - 1} - 1

。

2.3　预处理和后处理

由式（22），可知只要给出初始系数向量 $c_{n, j}$ （j=0，1，3，…， $2^{n} - 1$ ），便可通过迭代过程实现V-系统的各层分解；反之，通过式（23）可实现V-系统的信号重构。若信号具有解析表达式 $f (x)$ ，那么由式（15），可得初始系数向量。若实际信号以离散数据形式给出，则需经过预处理得到 $c_{n, j}$ ，j=0，1，3，…， $2^{n} - 1$ 。

假设信号 $f = [f_{0}, f_{1}, \dots, f_{N - 1}]^{T}$ ，其中 $N = (k + 1) 2^{n}$ 。若原信号长度小于N，可通过插值或结尾补零的方式扩充至N。为将离散数据转换为在基函数表达下的系数向量，通过对离散信号f进行分段k次多项式插值，而插值基函数就选前k+1个Lengdre多项式，那么插值系数便为初始系数向量。

记插值点位置为 $x_{i} = \frac{2 i + 1}{2 (k + 1)}$ ，i=0，1，…，k。第j组（j=0，1，3，…， $2^{n} - 1$ ）插值数据为

f_{j} = {[f_{(k + 1) j}, f_{(k + 1) j + 1}, \dots, f_{(k + 1) j + k}]}^{T}

，

则得到k+1阶线性方程组

\sqrt[]{2^{n}} A_{k} c_{n, j} = f_{j}

，（24）

其中，系数矩阵为

A_{k} = [\begin{matrix} φ_{k}^{0} (x_{0}) & φ_{k}^{1} (x_{0}) & \dots & φ_{k}^{k} (x_{0}) \\ φ_{k}^{0} (x_{1}) & φ_{k}^{1} (x_{1}) & \dots & φ_{k}^{k} (x_{1}) \\ ⋮ & ⋮ & ⋮ \\ φ_{k}^{0} (x_{k}) & φ_{k}^{1} (x_{k}) & \dots & φ_{k}^{k} (x_{k}) \end{matrix}] 。

对常见的k=1，2，3的情形，相应的系数矩阵 $A_{k}$ 为

\begin{array}{l} A_{1} = [\begin{matrix} 1 & \frac{\sqrt[]{3}}{2} \\ 1 & - \frac{\sqrt[]{3}}{2} \end{matrix}], A_{2} = [\begin{matrix} 1 & \frac{2 \sqrt[]{3}}{3} & \frac{\sqrt[]{5}}{6} \\ 1 & 0 & - \frac{\sqrt[]{5}}{2} \\ 1 & - \frac{2 \sqrt[]{3}}{3} & \frac{\sqrt[]{5}}{6} \end{matrix}], \\ A_{3} = [\begin{matrix} 1 & \frac{3 \sqrt[]{3}}{4} & \frac{11 \sqrt[]{5}}{32} & \frac{9 \sqrt[]{7}}{128} \\ 1 & \frac{\sqrt[]{3}}{4} & - \frac{13 \sqrt[]{5}}{32} & - \frac{43 \sqrt[]{7}}{128} \\ 1 & - \frac{\sqrt[]{3}}{4} & - \frac{13 \sqrt[]{5}}{32} & \frac{43 \sqrt[]{7}}{128} \\ 1 & - \frac{3 \sqrt[]{3}}{4} & \frac{11 \sqrt[]{5}}{32} & - \frac{9 \sqrt[]{7}}{128} \end{matrix}] 。 \end{array}

因此，易得

c_{n, j} = \frac{1}{\sqrt[]{2^{n}}} A_{k}^{- 1} f_{j}

。（25）

在实际计算中，可事先计算系数矩阵的逆矩阵 $A_{k}^{- 1}$ ，由式（25）得到初始系数向量 $c_{n, j}$ ，j=0，1，3，…， $2^{n} - 1$ 。反之，通过V-系统快速重构算法得到最终系数向量 $c_{n^{'}, j}$ ，j=0，1，3，…， $2^{n} - 1$ ，将其代入式（24），即可得到重构信号的离散点列，这便是后处理。

2.4　复杂度分析

假设信号长度 $N = (k + 1) 2^{n}$ ， $n \in N$ 。若采用传统的基于正交矩阵的V-系统变换，在预处理中，仅正交化过程的时间复杂度就高达 $Ο (N^{3})$ ，而在分解和重构过程中，时间复杂度均为 $Ο (N^{2})$ ，因此整个过程的时间复杂度为 $Ο (N^{3})$ 。

而对于本文的快速变换算法，在预处理（式（25））及后处理（式（24））中均只需要 $(k + 1) N$ 次乘法运算，其时间复杂度为 $Ο (N)$ 。在分解（式（22））和重构（式（23））过程中，每迭代一次，数据规模减半，因此共需 $2^{n - 1} + 2^{n - 2} + \dots + 2 + 1 \approx 2^{n}$ 个计算单元，每个计算单元涉及 $4 {(k + 1)}^{2}$ 次乘法，总共需要 $4 (k + 1) N$ 次乘法运算，因此快速算法的时间复杂度为 $Ο (N)$ 。

在空间复杂度方面，传统的V-系统变换算法，需要存储N×N阶变换矩阵，当值较大时，变换矩阵的存储亦是一大障碍。而本文的快速变换算法，只需存储4个k+1（k仅取1，2或3）阶的双尺度方程系数矩阵，存储代价可以忽略不计。

综上所述，本文提出的V-系统快速变换算法，无论是时间复杂度还是空间复杂度，都具有非常高的效率。

3　实验检测

实验1

根据前文分析，所设计的V-系统快速变换算法的时间复杂度为 $Ο (N)$ ，而传统的基于离散V矩阵变换算法的时间复杂度为 $Ο (N^{3})$ 。通过数值实验比较两者的差别。

如前所述，信号 $f$ 的长度 $N = (k + 1) 2^{n}$ ，因此，当次数k确定后（k=3），信号长度N由参数n决定。而参数n为V-系统分解或重构的层数。在分别选取n=5，6，…，12的情形下，随机生成长度N=128，256，…，16 384的信号，分别用传统变换算法和本文算法计算该信号的运行时间。其中，传统变换算法的运行时间为离散正交矩阵的生成、正变换及逆变换的时间之和，本文算法的运行时间为预处理、正变换（分解）、逆变换（重构）及后处理的时间之和，测试结果见表2。由表2可知，本文算法几乎能实时完成这样数据规模的信号变换，而传统变换算法需要花费非常长的时间。

表2 不同信号长度算法的运行时间

Table 2 Algorithm running time（in seconds） under different signal lengths

变换层数n	信号长度	运行时间/s
变换层数n	信号长度	传统算法	本文算法
5	128	0.015	0.000 50
6	256	0.038	0.000 56
7	512	0.135	0.000 78
8	1 024	1.05	0.000 67
9	2 048	56.85	0.000 73
10	4 096	203.3	0.001 60
11	8 192	1 709.54	0.003 70
12	16 384	12 876.13	0.009 00

注运行环境 Matlab R2020a；CPU：i7-8700K 3.70 GHz； RAM：32 GB。

新窗口打开| 下载CSV

实验2　为进一步显示快速算法在大规模数据处理中的应用潜力，选取由375条长度不等、形态各异的等高线组成的等高线簇数据（图1），这是一类典型的群组对象（由若干互相分离的单体构成的视觉整体），一共包含N=16，777，216个数据点。对该信号在V-系统下（k=3）分解至n=22层，得到信号在各分辨率下的分解系数 ${c_{0}, d_{0}, d_{1}, \dots, d_{22}}$ ；然后，利用分解系数对信号进行重构。整个过程的运行时间为1.895 s（其中，预处理时间0.150 s，分解时间0.901 s，重构时间0.812 s，后处理时间0.032 s）。而且，重构结果的精确性以及相应的图形（图2）验证了本文算法具有很好的数值稳定性。实验表明，所设计的V-系统快速变换算法对较大规模数据处理也具可行性。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 等高线簇图形

Fig.1 Contour cluster diagram

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 等高线簇的精确重构结果

Fig.2 Precise reconstruction results of contour clusters

4　结论

针对V-系统在处理大规模数据方面因高复杂度所造成的瓶颈问题，设计并实现了V-系统的快速变换算法。通过V-系统的多分辨率分析性质，得到各层子空间的具体关系，推导得到V-系统分解与重构的迭代公式。此外，针对实际应用中常以离散数据形式给出的信号，设计了相应的预处理和后处理，从而完成了V-系统快速变换的完整框架。通过理论分析，得到快速变换算法的计算复杂度仅为 $Ο (N)$ 。对实际大规模数据的测试结果表明，本文算法是有效的，为V-系统在更多领域的应用奠定了一定基础。

http://dx.doi.org/10.3785/j.issn.1008-9497.2023.06.001

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

SHENSA

The discrete wavelet transform： Wedding the a trous and Mallat algorithms

［J］. IEEE Transactions on Signal Processing， 1992， 40（10）： 2464-2482. DOI：10.1109/78.157290