2.624

2020影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

量子线性卷积及其在图像处理中的应用

刘兴奥 周日贵 郭文宇

刘兴奥, 周日贵, 郭文宇. 量子线性卷积及其在图像处理中的应用. 自动化学报, 2022, 48(6): 1504−1519 doi: 10.16383/j.aas.c210637
引用本文: 刘兴奥, 周日贵, 郭文宇. 量子线性卷积及其在图像处理中的应用. 自动化学报, 2022, 48(6): 1504−1519 doi: 10.16383/j.aas.c210637
Liu Xing-Ao, Zhou Ri-Gui, Guo Wen-Yu. Quantum linear convolution and its application in image processing. Acta Automatica Sinica, 2022, 48(6): 1504−1519 doi: 10.16383/j.aas.c210637
Citation: Liu Xing-Ao, Zhou Ri-Gui, Guo Wen-Yu. Quantum linear convolution and its application in image processing. Acta Automatica Sinica, 2022, 48(6): 1504−1519 doi: 10.16383/j.aas.c210637

量子线性卷积及其在图像处理中的应用

doi: 10.16383/j.aas.c210637
基金项目: 上海市科技项目(20040501500)资助
详细信息
    作者简介:

    刘兴奥:上海海事大学信息工程学院博士研究生. 主要研究方向为量子图像处理, 量子机器学习. E-mail: liuxingao@stu.shmtu.edu.cn

    周日贵:上海事大学信息工程学院教授. 主要研究方向为图像处理, 计算机视觉与模式识别. 本文通信作者. E-mail: rgzhou@shmtu.edu.cn

    郭文宇:上海海事大学信息工程学院博士研究生. 主要研究方向为量子机器学习, 量子计算和量子变分算法. E-mail: 202040310006@stu.shmtu.edu.cn

Quantum Linear Convolution and Its Application in Image Processing

Funds: Supported by Shanghai Science and Technology Project in 2020 (20040501500)
More Information
    Author Bio:

    LIU Xing-Ao Ph. D. candidate at the School of Information Engineering, Shanghai Maritime University. His research interest covers quantum image processing, quantum machine learning

    ZHOU Ri-Gui Professor at School of Information Engineering, Shanghai Maritime University. His research interest covers image processing, computer vision and pattern recognition. Corresponding author of this paper

    GUO Wen-Yu Ph. D. candidate at School of Information Engineering, Shanghai Maritime University. Her research interest covers quantum machine learning, quantum computing and quantum variational algorithm

  • 摘要: 线性卷积在图像处理中发挥着重要作用, 但是在处理海量高分辨率图像时, 求解线性卷积会消耗许多计算资源. 为此, 本文就量子线性卷积及其在图像处理问题中的应用开展相关研究, 首先提出单通道, 单位步长, 零补充情况下的量子一维和二维线性卷积, 然后实现多通道, 非单位步长, 非零补充的情况, 最后将量子二维线性卷积应用于量子图像平滑, 量子图像锐化和量子图像边缘检测. 通过理论分析证明了量子线性卷积的空间复杂度${\rm{O}}(\mathrm{log}M)$和时间复杂度${\rm{O}}({\mathrm{log}}^{2}M)$较经典线性卷积有指数级下降, 且基于Qiskit的仿真实验成功验证了量子线性卷积和量子图像处理算法的正确性和可行性.
    1)  1 https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/mean_filter.ipynb2 https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/gaussian_filter.ipynb3 SciPy 包: https: //docs.scipy.org/doc/scipy/reference/
    2)  2 https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/gaussian_filter.ipynb
    3)  3 SciPy 包: https: //docs.scipy.org/doc/scipy/reference/
    4)  4 https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/sharpen_filter.ipynb
    5)  5 https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/edge_extraction.ipynb
  • 图  1  量子一维线性卷积实现电路

    Fig.  1  Quantum circuit of one-dimensional linear convolution

    图  2  三通道/两步长的量子一维宽卷积实现电路

    Fig.  2  Three-channel/two-stride quantum one-dimensional wide convolution realization circuit

    图  3  量子图像平滑的实验图像和平滑滤波器

    Fig.  3  Experimental image and smoothing filter for quantum image smoothing

    图  4  量子图像平滑的仿真电路和仿真结果

    Fig.  4  Simulation circuit and simulation results of quantum image smoothing

    图  5  量子图像锐化的实验图像和锐化滤波器

    Fig.  5  Experimental image and sharpening filter for quantum image sharpening

    图  6  量子图像锐化的仿真电路和仿真结果

    Fig.  6  Simulation circuit and simulation results of quantum image sharpening

    图  7  量子图像边缘检测的实验图像和 Sobel 算子

    Fig.  7  Experimental image and Sobel operator of quantum image edge detection

    图  8  量子图像边缘检测的仿真电路和仿真结果

    Fig.  8  Simulation circuit and simulation results of quantum image edge detection

    A1  置换矩阵的量子电路

    A1  Quantum circuit of permutation matrix

    表  1  已被提出的量子图像滤波和量子图像特征边缘检测算法. 假设卷积核算子的尺寸为3 × 3,图像尺寸是 $M \times M$, $M = {2^m}$, q表示图像的灰度值范围

    Table  1  Quantum image filtering and quantum image feature edge detection algorithms have been proposed. Suppose the size of the convolution kernel operator is 3 × 3, and the image size is $M \times M$, $M = {2^m}$, q represents the range of gray values

    图像处理 图像编码 卷积核算子 邻域获取 空间复杂度 时间复杂度 论文
    图像滤波(平滑,锐化) NEQR 任意卷积核 第一种 18m + 9q O(9m2 + 9q2) [14]
    NEQR Gaussian核 第一种 20m+10q + 1 O(m222m + q222m) [15]
    NEQR 任意卷积核 第一种 18m + 9q O(9m2 + 9q2) [16]
    量子图像边缘检测 NEQR Sobel 第二种 4m+18q O(m2 + q2) [18]
    NEQR Kirsch 第一种 18m + 9q O(m2 + 2q+3) [19]
    NEQR Zero-cross 第二种 2m + 9q O(m2 + q2) [20]
    GQIR Sobel 第一种 18m + 9q O(m2 + 2q+5 + q2) [21]
    NEQR Prewitt 第一种 18m + 9q O(m2 + 2q+3) [22]
    NEQR Sobel 第二种 2m + 9q O(m2 + 2q+4) [23]
    NEQR Sobel 第二种 2m + 9q O(10m2 + 4q2) [24]
    NEQR Sobel 第一种 18m + 9q O(qm2 + 9q3) [25]
    FRQ Sobel 第二种 2m + 9q O(10m2 + q2) [26]
    FRQI Sobel 第二种 4m + 10 O(10m2 + q2) [28]
    NEQR Canny 第三种 18m + 9q O(48m2 + 4q2) [29]
    下载: 导出CSV
  • [1] Gonzalez R C, Woods R E[著], 阮秋琦, 阮宇智[译]. 数字图像处理. 第3版. 北京: 电子工业出版社, 2017.

    Gonzalez R C, Woods R E[Author], Ruan Qiu-Qi, Ruan Yu-Zhi[Translator]. Digital Image Processing (Third edition). Beijing: Publishing House of Electronics Industry, 2017.
    [2] 盖杉, 鲍中运. 基于深度学习的高噪声图像去噪算法. 自动化学报, 2020, 46(12): 2672-2680

    Gai Shan, Bao Zhong-Yun. High noise image denoising algorithm based on deep learning. Acta Automatica Sinica, 2020, 46(12): 2672-2680
    [3] Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. Santa Fe, USA: IEEE, 1994. 124−134
    [4] Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. Philadelphia, USA: Association for Computing Machinery, 1996. 212−219
    [5] Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Physical Review Letters, 2009, 103(15): Article No. 150502
    [6] 段隆振, 谢旭明, 邱桃荣, 杨舒晴. 基于量子计算的粗糙集核属性求解算法. 自动化学报, 2020, 46(8): 1753-1758

    Duan Long-Zhen, Xie Xu-Ming, Qiu Tao-Rong, Yang Shu-Qing. A quantum algorithm of the computation of core in rough set. Acta Automatica Sinica, 2020, 46(8): 1753-1758
    [7] Huang H Y, Broughton M, Mohseni M, Babbush R, Boixo S, Neven H, et al. Power of data in quantum machine learning. Nature Communications, 2021, 12: Article No. 2631
    [8] Ye Z K, Li L Z, Situ H Z, Wang Y Y. Quantum speedup of twin support vector machines. Science China Information Sciences, 2020, 63(8): Article No. 189501
    [9] 黄一鸣, 雷航, 李晓瑜. 量子机器学习算法综述. 计算机学报, 2018, 41(1): 145-163 doi: 10.11897/SP.J.1016.2018.00145

    Huang Yi-Ming, Lei Hang, Li Xiao-Yu. A survey on quantum machine learning. Chinese Journal of Computers, 2018, 41(1): 145-163 doi: 10.11897/SP.J.1016.2018.00145
    [10] Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S. Quantum machine learning. Nature, 2017, 549(7671): 195-202 doi: 10.1038/nature23474
    [11] Lomont C. Quantum convolution and quantum correlation algorithms are physically impossible [Online], available: https://arxiv.org/abs/quant-ph/0309070, November 5, 2021
    [12] 闫茜茜, 王鹏程, 刘兴云. 一维量子卷积计算. 计算机工程与应用, 2020, 56(8): 55-59 doi: 10.3778/j.issn.1002-8331.1911-0097

    Yan Xi-Xi, Wang Peng-Cheng, Liu Xing-Yun. One-dimensional quantum convolution calculation. Computer Engineering and Applications, 2020, 56(8): 55-59 doi: 10.3778/j.issn.1002-8331.1911-0097
    [13] 闫茜茜, 王鹏程, 刘兴云. 二维量子卷积计算. 量子光学学报, 2020, 26(4): 327-333

    Yan Xi-Xi, Wang Peng-Cheng, Liu Xing-Yun. Two dimensional quantum convolution calculation. Journal of Quantum Optics, 2020, 26(4): 327-333
    [14] Yuan S Z, Lu Y L, Mao X F, Luo Y, Yuan J G. Improved quantum image filtering in the spatial domain. International Journal of Theoretical Physics, 2018, 57(3): 804-813 doi: 10.1007/s10773-017-3614-1
    [15] Li P C, Liu X D, Xiao H. Quantum image weighted average filtering in spatial domain. International Journal of Theoretical Physics, 2017, 56(11): 3690-3716 doi: 10.1007/s10773-017-3533-1
    [16] Yuan S Z, Mao X F, Zhou J, Wang X F. Quantum image filtering in the spatial domain. International Journal of Theoretical Physics, 2017, 56(8): 2495-2511 doi: 10.1007/s10773-017-3403-x
    [17] Wang Z B, Xu M Z, Zhang Y N. Review of quantum image processing. Archives of Computational Methods in Engineering, 2022, 29(2): 737-761 doi: 10.1007/s11831-021-09599-2
    [18] Chetia R, Boruah S M B, Sahu P P. Quantum image edge detection using improved Sobel mask based on NEQR. Quantum Information Processing, 2021, 20(1): Article No. 21
    [19] Xu P G, He Z X, Qiu T H, Ma H Y. Quantum image processing algorithm using edge extraction based on Kirsch operator. Optics Express, 2020, 28(9): 12508-12517 doi: 10.1364/OE.386283
    [20] Fan P, Zhou R G, Hu W W, Jing N H. Quantum image edge extraction based on Laplacian operator and zero-cross method. Quantum Information Processing, 2019, 18(1): Article No. 27
    [21] Zhou R G, Liu D Q. Quantum image edge extraction based on improved Sobel operator. International Journal of Theoretical Physics, 2019, 58(9): 2969-2985 doi: 10.1007/s10773-019-04177-6
    [22] Zhou R G, Yu H, Cheng Y, Li F X. Quantum image edge extraction based on improved Prewitt operator. Quantum Information Processing, 2019, 18(9): Article No. 261
    [23] Fan P, Zhou R G, Hu W W, Jing N H. Quantum image edge extraction based on classical Sobel operator for NEQR. Quantum Information Processing, 2019, 18(1): Article No. 24
    [24] Chetia R, Boruah S M B, Roy S, Sahu P P. Quantum image edge detection based on four directional Sobel operator. In: Proceedings of the 8th International Conference on Pattern Recognition and Machine Intelligence. Tezpur, India: Springer, 2019. 532−540
    [25] Yuan S Z, Venegas-Andraca S W, Wang Y C, Luo Y, Mao X F. Quantum image edge detection algorithm. International Journal of Theoretical Physics, 2019, 58(9): 2823-2833 doi: 10.1007/s10773-019-04166-9
    [26] Lu Z Y, Wang X M, Shang J Z, Luo Z R, Sun C F, Wu G H. A multimedia image edge extraction algorithm based on flexible representation of quantum. Multimedia Tools and Applications, 2019, 78(17): 24067-24082 doi: 10.1007/s11042-019-7173-8
    [27] Yao X W, Wang H Y, Liao Z Y, Chen M C, Pan J, Li J, et al. Quantum image processing and its application to edge detection: Theory and experiment. Pysical Review X, 2017, 7(3): Article No. 031041
    [28] Zhang Y, Lu K, Gao Y H. QSobel: A novel quantum image edge extraction algorithm. Science China Information Sciences, 2015, 58(1): 1-13
    [29] 胡文文, 周日贵, 范萍, 李尧翀. 基于Canny算法的量子图像边缘检测. 郑州大学学报(理学版), 2020, 52(4): 37-52

    Hu Wen-Wen, Zhou Ri-Gui, Fan Ping, Li Yao-Chong. Quantum image edge detection based on Canny algorithm. Journal of Zhengzhou University (Natural Science Edition), 2020, 52(4): 37-52
    [30] Fan P, Zhou R G, Jing N H, Li H S. Geometric transformations of multidimensional color images based on NASS. Information Sciences, 2016, 340-341: 191-208 doi: 10.1016/j.ins.2015.12.024
    [31] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. New York: Cambridge University Press, 2010. 171−211
    [32] 唐雅茹, 丛爽, 杨靖北. 单量子比特系统状态的在线估计. 自动化学报, 2020, 46(8): 1592-1599

    Tang Ya-Ru, Cong Shuang, Yang Jing-Bei. On-line state estimation of one-qubit system. Acta Automatica Sinica, 2020, 46(8): 1592-1599
    [33] Giovannetti V, Lloyd S, Maccone L. Quantum random access memory. Physical Review Letters, 2008, 100(16): Article No. 160501
    [34] Giovannetti V, Lloyd S, Maccone L. Architectures for a quantum random access memory. Physical Review A, 2008, 78(5): Article No. 052310
    [35] Arunachalam S, Gheorghiu V, Jochym-O'Connor T, Mosca M, Srinivasan P V. On the robustness of bucket brigade quantum RAM. New Journal of Physics, 2015, 17: Article No. 123010
    [36] Kerenidis I, Prakash A. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing, 2020, 1(1): Article No. 5
    [37] Brassard G, Hoyer P, Mosca M, Tapp A. Quantum amplitude amplification and estimation [Online], available: https://arxiv.org/abs/quant-ph/0005055v1, November 5, 2021
    [38] Mitarai K, Kitagawa M, Fujii K. Quantum analog-digital conversion. Physical Review A, 2019, 99(1): Article No. 012301
    [39] Shao C P, Li Y, Li H B. Quantum algorithm design: Techniques and applications. Journal of Systems Science and Complexity, 2019, 32(1): 375-452 doi: 10.1007/s11424-019-9008-0
    [40] Zhou S S, Wang J B. Efficient quantum circuits for dense circulant and circulant like operators. Royal Society Open Science, 2017, 4(5): Article No. 160906
    [41] Buhrman H, Cleve R, Watrous J, de Wolf R. Quantum fingerprinting. Physical Review Letters, 2001, 87(16): Article No. 167902
    [42] Shao C P. Quantum algorithms to matrix multiplication [Online], available: https://arxiv.org/abs/1803.01601v2, November 5, 2021
    [43] McKay D C, Alexander T, Bello L, Biercuk M J, Bishop L, Chen J, et al. Qiskit backend specifications for openQASM and openPulse experiments [Online], available: https://arxiv.org/abs/1809.03452v1, November 5, 2021
    [44] 高敏娟, 党宏社, 魏立力, 王海龙, 张选德. 结合全局与局部变化的图像质量评价. 自动化学报, 2020, 46(12): 2662-2671

    Gao Min-Juan, Dang Hong-She, Wei Li-Li, Wang Hai-Long, Zhang Xuan-De. Combining global and local variation for image quality assessment. Acta Automatica Sinica, 2020, 46(12): 2662-2671
    [45] 王冬, 刘志昊, 朱皖宁, 李善治. 基于多目标扩展通用Toffoli门的量子比较器设计. 计算机科学, 2012, 39(9): 302-306 doi: 10.3969/j.issn.1002-137X.2012.09.069

    Wang Dong, Liu Zhi-Hao, Zhu Wan-Ning, Li Shan-Zhi. Design of quantum comparator based on extended general Toffoli gates with multiple targets. Computer Science, 2012, 39(9): 302-306 doi: 10.3969/j.issn.1002-137X.2012.09.069
    [46] Xia H Y, Xiao Y F, Song S X, Li H S. Quantum circuit design of approximate median filtering with noise tolerance threshold. Quantum Information Processing, 2020, 19(6): Article No. 183
    [47] Jiang S X, Zhou R G, Hu W W, Li Y C. Improved quantum image median filtering in the spatial domain. International Journal of Theoretical Physics, 2019, 58(7): 2115-2133 doi: 10.1007/s10773-019-04103-w
    [48] Li P C, Liu X D, Xiao H. Quantum image median filtering in the spatial domain. Quantum Information Processing, 2018, 17(3): Article No. 49
    [49] 赵娅, 郭嘉慧, 李盼池. 一种量子图像的中值滤波方案. 电子与信息学报, 2021, 43(1): 204-211 doi: 10.11999/JEIT191038

    Zhao Ya, Guo Jia-Hui, Li Pan-Chi. A median filtering scheme for quantum images. Journal of Electronics & Information Technology, 2021, 43(1): 204-211 doi: 10.11999/JEIT191038
    [50] Ali A E, Abdel-Galil H, Mohamed S. Quantum image mid-point filter. Quantum Information Processing, 2020, 19(8): Article No. 238
    [51] Fijany A, Williams C P. Quantum wavelet transforms: Fast algorithms and complete circuits. In: Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications (QCQC). Palm Springs, USA: Springer, 1999. 10−33
    [52] 王冬, 刘强, 李善治. 基于矩阵初等变换的量子可逆逻辑电路双向综合算法. 计算机科学, 2014, 41(9): 18-23 doi: 10.11896/j.issn.1002-137X.2014.09.002

    Wang Dong, Liu Qiang, Li Shan-Zhi. Bidirectional reversible logic circuit synthesis algorithm based on matrix elementary transformation. Computer Science, 2014, 41(9): 18-23 doi: 10.11896/j.issn.1002-137X.2014.09.002
    [53] Le P Q, Iliyasu A M, Dong F Y, Hirota K. Strategies for designing geometric transformations on quantum images. Theoretical Computer Science, 2011, 412(15): 1406-1418 doi: 10.1016/j.tcs.2010.11.029
    [54] Zhang Y, Lu K, Gao Y H, Wang M. NEQR: A novel enhanced quantum representation of digital images. Quantum Information Processing, 2013, 12(8): 2833-2860 doi: 10.1007/s11128-013-0567-z
    [55] Cortese J A, Braje T M. Loading classical data into a quantum computer [Online], available: https://arxiv.org/abs/1803.01958v1, November 5, 2021
    [56] Li H S, Zhu Q X, Zhou R G, Li M G, Song L, Ian H. Multidimensional color image storage, retrieval, and compression based on quantum amplitudes and phases. Information Sciences, 2014, 273: 212-232 doi: 10.1016/j.ins.2014.03.035
    [57] Le P Q, Dong F Y, Hirota K. A flexible representation of quantum images for polynomial preparation, image compression, and processing operations. Quantum Information Processing, 2011, 10(1): 63-84 doi: 10.1007/s11128-010-0177-y
    [58] Grover L, Rudolph T. Creating superpositions that correspond to efficiently integrable probability distributions [Online], available: https://arxiv.org/abs/quant-ph/0208112v1, November 5, 2021
    [59] Kerenidis I, Prakash A. Quantum recommendation systems. In: Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS). Berkeley, USA: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017. 1−21
    [60] Jiang N, Wang J, Mu Y. Quantum image scaling up based on nearest-neighbor interpolation with integer scaling ratio. Quantum Information Processing, 2015, 14(11): 4001-4026 doi: 10.1007/s11128-015-1099-5
    [61] Li H S, Song S X, Fan P, Peng H L, Xia H Y, Liang Y. Quantum vision representations and multi-dimensional quantum transforms. Information Sciences, 2019, 502: 42-58 doi: 10.1016/j.ins.2019.06.037
    [62] Liu K, Zhang Y, Wang X P, Lu K. A strategy of quantum image filtering in frequency domain. In: Proceedings of the 2016 International Conference on Applied Mechanics, Electronics and Mechatronics Engineering (AMEME). Beijing, China: DEStech, 2016. 82−87
    [63] Situ H Z, He Z M, Wang Y Y, Li L Z, Zheng S G. Quantum generative adversarial network for generating discrete distribution. Information Sciences, 2020, 538: 193-208 doi: 10.1016/j.ins.2020.05.127
  • 加载中
计量
  • 文章访问数:  246
  • HTML全文浏览量:  156
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-07-08
  • 网络出版日期:  2021-12-13

目录

    /

    返回文章
    返回