<i>V</i>-系统的快速变换算法

doi:10.3785/j.issn.1008-9497.2023.06.011

浙江大学学报（理学版）

2023, Vol. 50

Issue (6): 761-769 DOI: 10.3785/j.issn.1008-9497.2023.06.011

第15届全国几何设计与计算学术会议专题

V-系统的快速变换算法

陈伟¹(

),戚谨雯¹,李坚²,宋瑞霞³

^1.江南大学人工智能与计算机学院，江苏无锡 214122
^2.澳门理工大学应用科学学院，澳门 999078
^3.北方工业大学理学院，北京 100144

A fast algorithm for V-system

Wei CHEN¹(

),Jinwen QI¹,Jian LI²,Ruixia SONG³

^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

全文: PDF(1706 KB)

HTML( 0 )

摘要：

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.

Key words: V-system orthogonal resolution analysis double scale equation multi wavelet fast algorithm

收稿日期: 2023-06-21 出版日期: 2023-11-30

CLC:

TP 391

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

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	陈伟
	戚谨雯
	李坚
	宋瑞霞

引用本文:

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

Wei CHEN,Jinwen QI,Jian LI,Ruixia SONG. A fast algorithm for V-system. Journal of Zhejiang University (Science Edition), 2023, 50(6): 761-769.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2023.06.011 或 https://www.zjujournals.com/sci/CN/Y2023/V50/I6/761

$k$	$V$ 系统
注释	尺度空间 $V 0$ $? k 0 x, ? k 1 x, ???? ?, ? k k x$	小波空间 $W 0$ $ψ k, 0 0,0 x, ψ k, 0 0,1 x, ???? ?, ψ k, 0 0, k x$	小波空间 $W 1$ $ψ k, 1 j, i x = 2 ψ k, 0 0, i (2 x - j), ???? x ∈ j 2, j + 1 2, 0, ???? 其他,$ $i = 0,1, 2, ?, k; j = 0,1$	小波空间 $W 2$ $ψ k, 2 j, i x = 2 ψ k, 0 0, i (4 x - j), ???? x ∈ j 4, j + 1 4, 0, ???? 其他,$ $i = 0,1, 2 ， ?, k; j = 0,1, 2,3$	小波空间 $W n$ $ψ k, n j, i x = 2 ψ k, 0 0, i (2 n x - j), ???? x ∈ j 2 n, j + 1 2 n, 0, ???? 其他,$ $i = 0,1, 2 ， ?, k; j = 0,1, 3 ， ?, 2 n - 1$
0					…
1					…
2					…
3					…

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

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

图1 等高线簇图形

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

1	SHENSA M. 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 doi: 10.1109/78.157290
2	BLAHUT R E. Fast Algorithms for Signal Processing［M］. Cambridge： Cambridge University Press， 2010. doi:10.1017/cbo9780511760921 doi: 10.1017/cbo9780511760921
3	LEZCANO-CASADO M， MARTINEZ-RUBIO D. Cheap orthogonal constraints in neural networks： A simple parametrization of the orthogonal and unitary group［C］// International Conference on Machine Learning. Long Beach ：PMLR， 2019： 3794-3803. doi:10.48550/arXiv.1901.08428 doi: 10.48550/arXiv.1901.08428
4	SHAH S B， CHAKKA V K， REDDY A S. Orthogonal and non-orthogonal signal representations using new transformation matrices having NPM structure［J］. IEEE Transactions on Signal Processing， 2020， 68： 1229-1242. DOI：10.1109/tsp.2020.2971936 doi: 10.1109/tsp.2020.2971936
5	FEDORENKO S V. Duhamel/Hollmann-like discrete fourier transform algorithm with the smallest multiplicative complexity over a finite field［J］. IEEE Transactions on Signal Processing， 2020， 68： 4813-4823. DOI：10.1109/tsp.2020.3015419 doi: 10.1109/tsp.2020.3015419
6	MA H， QI D X， SONG R X， et al. The complete orthogonal V-system and its applications［J］. Communications on Pure and Applied Analysis， 2007， 6（3）： 853-871. DOI：10.3934/cpaa.2007.6.853 doi: 10.3934/cpaa.2007.6.853
7	齐东旭，宋瑞霞，李坚. 非连续正交函数： U-系统， V-系统，多小波及其应用［M］. 北京：科学出版社， 2011. QI D X， SONG R X， LI J. Discontinuous Orthogonal Function： U-System， V-System， Multiwavelet and Its Application［M］. Beijing： Science Press， 2011
8	李坚，宋瑞霞，叶梦杰，等. 基于三角域上V-系统的三维几何模型的正交重构［J］. 计算机学报， 2009， 32（2）： 193-202. DOI：10.3724/SP.J.1016.2009. 00193 LI J， SONG R X， YE M J， et al. Orthogonal reconstruction of 3D model based on V-system over triangular domain［J］. Journal of Computer Science and Technology， 2009， 32（2）： 193-202. DOI：10. 3724/SP.J.1016.2009.00193 doi: 10. 3724/SP.J.1016.2009.00193
9	YE B， YUAN X X， CAI Z C， et al. Severity assessment of COVID-19 based on feature extraction and V-descriptors［J］. IEEE Transactions on Industrial Informatics， 2021， 17（11）： 7456-7467. DOI：10. 1109/TII.2021.3056386 doi: 10. 1109/TII.2021.3056386
10	SONG R X， YAO D X， WANG X C， et al. Retrieval method for 3D object group based on V-system［J］. Journal of Advanced Mechanical Design， Systems， and Manufacturing， 2012， 6（3）： 340-353. DOI：10. 1299/JAMDSM.6.340 doi: 10. 1299/JAMDSM.6.340
11	WANG Z H， LIN H W. 3D shape retrieval based on Laplace operator and joint Bayesian model［J］. Visual Informatics， 2020， 4 （3）： 69-76. DOI：10.1016/j.visinf.2020.08.002 doi: 10.1016/j.visinf.2020.08.002
12	陈伟，张晓婷. 正交旋转不变V矩及其在图像重建中的应用［J］. 自动化学报， 2015， 41（2）： 376-385. DOI：10.16383/j.aas.2015.c140347 CHEN W， ZHANG X T. Orthogonal rotation-invariant V moments and application to image reconstruction［J］. IEEE/CAA Journal of Automatica Sinica， 2015， 41（2）： 376-385. DOI：10. 16383/j.aas.2015.c140347 doi: 10. 16383/j.aas.2015.c140347
13	宋传鸣，赵长伟，刘丹，等. 3D 多尺度几何分析研究进展［J］. 软件学报， 2015， 26（5）： 1213-1236. DOI：10.13328/j.cnki.jos.004822 SONG C M， ZHAO C W， LIU D， et al. Advances in three-dimensional multiscale geometrical analysis［J］. Journal of Software， 2015， 26（5）： 1213-1236. DOI：10.13328/j.cnki.jos.004822 doi: 10.13328/j.cnki.jos.004822
14	CAO W， MENG Z G， LI A J， et al. Thermal features of lunar regolith in mare humboldtianum based on brightness temperature differences and surface parameters［J］. Authorea Preprints， 2022. DOI：10. 1002/essoar.10505601.1 doi: 10. 1002/essoar.10505601.1
15	王小春，宋瑞霞. 一类正交函数系的离散表示及快速变换［J］. 计算机工程与应用， 2008， 44（8）： 40-44. doi:10.3778/j.issn.1002-8331.2008.08.012 WANG X C， SONG R X. Discrete representation and fast algorithm of new class of orthogonal system［J］. Computer Engineering and Applications， 2008， 44（8）： 40-44. doi:10.3778/j.issn.1002-8331.2008.08.012 doi: 10.3778/j.issn.1002-8331.2008.08.012
16	宋瑞霞，孙坦坦，孙相东，等. 广义V-系统的构造及相应的快速变换［J］. 计算机辅助设计与图形学学报， 2018， 30（5）： 808-815. DOI：10.3724/SP.J.1089. 2017.16644 SONG R X， SUN T T， SUN X D， et al. The construction of generalized V-system and the corresponding fast transformation［J］. Journal of Computer-Aided Design & Computer Graphics， 2018， 30（5）： 808-815. DOI：10.3724/SP.J.1089. 2017.16644 doi: 10.3724/SP.J.1089. 2017.16644
17	HUANG C， YANG L， QI D X. A new class of multi-wavelet bases： V-system［J］. Acta Mathematica Sinica， 2012， 28（1）： 105-120. DOI：10.1007/s10114-012-9424-8 doi: 10.1007/s10114-012-9424-8
18	陈伟，蔡占川，齐东旭，等. 从GF-系统到V-系统：V-系统的一种新的构造方法［J］. 澳门科技大学学报， 2009， 3（2）： 8-14. CHEN W， CAI Z C， QI D X， et al. From GF-system to V-system： A new construction method of V-system［J］. Journal of Macau University of Science and Technology， 2009， 3（2）： 8-14.
19	宋瑞霞，李成华，王小春，等. V-系统的小波函数的数学结构［J］. 中国科学（数学）， 2016（6）： 867-876. SONG R X， LI C H， WANG X C， et al. Mathematical structure of wavelet functions of the V-system［J］. Scientia Sinica（Mathematica）， 2016（6）： 867-876.

[1]	张沛全,许威威. 哈希编码优化的IRON逆渲染模型：重建几何与材质[J]. 浙江大学学报（理学版）, 2023, 50(6): 754-760.
[2]	程天琪,王雷,郭新萍,王钰帏,刘春香,李彬. LK-CAUNet：基于交叉注意的大内核多尺度可变形医学图像配准网络[J]. 浙江大学学报（理学版）, 2023, 50(6): 745-753.
[3]	窦丰,马会文,谢昕洋,杨万文,石雪,韩丽,林彬. 广义无监督函数映射学习的三维形状密集对应方法[J]. 浙江大学学报（理学版）, 2023, 50(6): 736-744.
[4]	夏兆辉,刘健力,高百川,聂涛,余琛,陈龙,余金桂. 面向多尺度拓扑优化的渐进均匀化GPU并行算法研究[J]. 浙江大学学报（理学版）, 2023, 50(6): 722-735.
[5]	汪飞,李伟鸿,杨彧,姜大志,赵宝全,罗笑南. 动脉粥样硬化斑块生成的高效流固耦合不可压缩SPH模拟方法[J]. 浙江大学学报（理学版）, 2023, 50(6): 711-721.
[6]	张泽初,彭伟龙,唐可可,余朝阳,Khan Asad,方美娥. 面向CBCT图像的金字塔微分同胚变形牙齿网格重建方法[J]. 浙江大学学报（理学版）, 2023, 50(6): 701-710.
[7]	毛涵杨,彭晨,李晨,王长波. 面向开放表面的神经移动立方体算法[J]. 浙江大学学报（理学版）, 2023, 50(6): 692-700.
[8]	苏科华,刘百略,雷娜,李可涵,顾险峰. 基于最优质量传输的Focus+Context可视化[J]. 浙江大学学报（理学版）, 2023, 50(6): 681-691.
[9]	刘圣军,滕子,王海波,刘新儒. 基于函数映射的二维形状内蕴对称检测算法[J]. 浙江大学学报（理学版）, 2023, 50(6): 668-680.
[10]	刘泽润,尹宇飞,薛文灏,郭蕊,程乐超. 基于扩散模型的条件引导图像生成综述[J]. 浙江大学学报（理学版）, 2023, 50(6): 651-667.
[11]	谭晓东,赵奇,文明珠,王小超. 基于BEMD、DCT和SVD的混合图像水印算法[J]. 浙江大学学报（理学版）, 2023, 50(4): 442-454.
[12]	方于华,叶枫. MFDC-Net：一种融合多尺度特征和注意力机制的乳腺癌病理图像分类算法[J]. 浙江大学学报（理学版）, 2023, 50(4): 455-464.
[13]	孔翔,陈军. 一类带4个形状参数的同次三角曲面构造算法[J]. 浙江大学学报（理学版）, 2023, 50(2): 153-159.
[14]	张远鹏, 陈鸿韬, 王伟娜. 基于非凸非光滑变分模型的灰度图像泊松噪声移除算法[J]. 浙江大学学报（理学版）, 2023, 50(2): 160-166.
[15]	李军成,刘成志,罗志军,龙志文. 空间参数曲线的双目标能量极小化方法及其应用[J]. 浙江大学学报（理学版）, 2023, 50(1): 63-68.

Viewed

Full text

Abstract

Cited

Shared

Discussed