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

刘兴奥; 周日贵; 郭文宇

doi:10.16383/j.aas.c210637

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

doi: 10.16383/j.aas.c210637

刘兴奥^{1, 2},
周日贵^{1, 2,},
郭文宇^{1, 2}

1.
上海海事大学信息工程学院上海 201306
2.
上海海事大学智能信息处理与量子智能计算研究中心上海 201306

基金项目: 上海市科技项目(20040501500)资助

详细信息

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

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

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

计量
- 文章访问数: 1035
- HTML全文浏览量: 443
- PDF下载量: 249
- 被引次数: 0
出版历程
- 收稿日期: 2021-07-08
- 网络出版日期: 2021-12-13
- 刊出日期: 2022-06-02

Quantum Linear Convolution and Its Application in Image Processing

LIU Xing-Ao^{1, 2},
ZHOU Ri-Gui^{1, 2
,},
GUO Wen-Yu^{1, 2}

1.
College of Information Engineering, Shanghai Maritime University, Shanghai 201306
2.
Research Center of Intelligent Information Processing and Quantum Intelligent Computing, Shanghai 201306

Funds: Supported by Shanghai Science and Technology Project (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的仿真实验成功验证了量子线性卷积和量子图像处理算法的正确性和可行性.
- 量子线性卷积 /
- 量子图像平滑 /
- 量子图像锐化 /
- 量子图像边缘检测
Abstract: Linear convolution plays an important role in image processing, but when processing massive high-resolution images, solving linear convolution will consume a lot of computing resources. To this end, this paper conducts related research on quantum linear convolution and its application in image processing problems. We first propose the quantum one-dimensional and two-dimensional linear convolution in the case of single channel, unit stride and zero padding, and then implement the case of multi channel, non-unit stride and non-zero padding. Finally, we apply the quantum two-dimensional linear convolution to quantum image smoothing, quantum image sharpening and quantum image edge detection. Through theoretical analysis, it is proved that the space complexity ${\rm{O}}(\mathrm{log}M)$ and time complexity ${\rm{O}}({\mathrm{log}}^{2}M)$ of quantum linear convolution decrease exponentially compared with classical linear convolution, and the simulation experiment based on Qiskit successfully verifies the correctness and feasibility of the quantum linear convolution and quantum image processing algorithms.
- Quantum linear convolution /
- quantum image smoothing /
- quantum image sharpening /
- quantum image edge detection
注释:

1) ¹ https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/mean_filter.ipynb² https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/gaussian_filter.ipynb³ SciPy 包: https: //docs.scipy.org/doc/scipy/reference/

2) ² https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/gaussian_filter.ipynb

3) ³ SciPy 包: https: //docs.scipy.org/doc/scipy/reference/

4) ⁴ https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/sharpen_filter.ipynb

5) ⁵ https: //github.com/liuxingao/SimulateCode/blob/main/NORMAL/edge_extraction.ipynb

HTML全文

图 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(9m² + 9q²)	[14]
	NEQR	Gaussian核	第一种	20m+10q + 1	O(m²2^2m + q²2^2m)	[15]
	NEQR	任意卷积核	第一种	18m + 9q	O(9m² + 9q²)	[16]
量子图像边缘检测	NEQR	Sobel	第二种	4m+18q	O(m² + q²)	[18]
	NEQR	Kirsch	第一种	18m + 9q	O(m² + 2q⁺³)	[19]
	NEQR	Zero-cross	第二种	2m + 9q	O(m² + q²)	[20]
	GQIR	Sobel	第一种	18m + 9q	O(m² + 2^q+5 + q²)	[21]
	NEQR	Prewitt	第一种	18m + 9q	O(m² + 2^q+3)	[22]
	NEQR	Sobel	第二种	2m + 9q	O(m² + 2^q+4)	[23]
	NEQR	Sobel	第二种	2m + 9q	O(10m² + 4q²)	[24]
	NEQR	Sobel	第一种	18m + 9q	O(qm² + 9q³)	[25]
	FRQ	Sobel	第二种	2m + 9q	O(10m² + q²)	[26]
	FRQI	Sobel	第二种	4m + 10	O(10m² + q²)	[28]
	NEQR	Canny	第三种	18m + 9q	O(48m² + 4q²)	[29]

下载: 导出CSV

参考文献(63)

[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]	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
[52]	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
[53]	王冬, 刘强, 李善治. 基于矩阵初等变换的量子可逆逻辑电路双向综合算法. 计算机科学, 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
[54]	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
[55]	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
[56]	Cortese J A, Braje T M. Loading classical data into a quantum computer [Online], available: https://arxiv.org/abs/1803.01958v1, November 5, 2021
[57]	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
[58]	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
[59]	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
[60]	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
[61]	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
[62]	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
[63]	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