本期继续解读文献[1]:量子图像处理及其应用:边缘检测。

前期回顾

本期大纲

量子边缘检测算法QHED。主要包括以下4个部分:

  • QHED算法核心操作;
  • QHED算法输出分析;
  • QHED算法数值分析;
  • QHED算法实验验证。

量子边缘检测算法QHED

一个典型的图像处理任务是识别图像的边界,即识别图像中两个相邻领域的边界。如下图所示,这个任务不仅对数字图像处理有很重要的作用,同样适用于大脑的工作机制(大脑通过不同的神经元对线和边界的反应来处理视觉信息),在很多模式识别任务中都是很重要的一步操作。

量子图像处理及其应用:边缘检测(五)-量子客
经典的边缘检测方法主要是通过不同滤波模版计算图像梯度。因此,考虑到每一个像素都需要被处理,所有经典算法的时间复杂度至少为O(2^n)。文献[2]提出了一种量子算法,相比经典的边缘检测算法达到了指数加速。这个算法包括一个COPY操作和一个用于同时计算所有像素梯度的量子黑箱。但是对于这两步操作,目前还没有有效的操作可以实现。基于前几期提到的QImR,文献[1]提出了一个高效的量子算法能够在O(1)时间内找到两个区域的边界,这个时间复杂度独立于图像的大小。

QHED算法核心操作

这个方法主要是通过一个Hadamard门(H门)来检测边界。下图简单介绍了H门对量子态的最后一个比特作用的效果:

量子图像处理及其应用:边缘检测(五)-量子客

我们沿着黄色箭头方向来看:

首先,H门作用在|0>或|1>比特上会将其变为均衡叠加态。在图像列向量中任何一对相邻像素的位置可以通过图中蓝色二进制序列表示,像素值可以通过图中红色系数表示。

因此H门作用在图像的最后一个量子比特上,会将该量子比特的系数变为$C_{b_1\dotsc{b_{n-1}}0}\pm{C_{b_1\dotsc{b_{n-1}}1}}$。

图中右下角给出了H门作用在最后一个量子比特时整个系统所执行的酉算子:即对量子态的前n-1个量子比特执行单位矩阵,对最后一个量子比特执行H门。

通过执行该运算,可以得到输出图像的状态表示(变换过程如图中右上角方框所示)。

QHED算法输出分析

这里,我们感兴趣的输出部分是:

$C_{b_1\dotsc{b_{n-1}}0}-C_{b_1\dotsc{b_{n-1}}1}$

即我们对结果状态的偶数部分感兴趣:

  • 如果两个像素属于同一个区域,它们的亮度值(intensity values)是相同的,此时差为0
  • 否则差不为0,说明这是一个边界
  • 注意:我们可以对灰度值的差设置一个阈值,当差值小于这个阈值时,可以认为这个差值为0。

偶数位置的边界信息可以通过测量最后一个量子比特来提取。当测量最后一个量子的输出为1时,剩余前n-1个量子比特编码了图像的边界信息。因此,这个过程在像素之间产生了水平边界,位置在0/1,2/3等。

为了同样获得位置1/2,3/4等的边界,文献[1]对输入的图像状态执行了一个n量子比特的概率幅置换(amplitude permutation)操作,产生一个新的图像状态|f’〉,其中奇数(偶数)元素等于输入|f〉的偶数(奇数)部分。

概率幅置换(amplitude permutation)可以在$O[poly(n)]$时间内有效执行[3]。

此时对新的图像状态|f’〉执行单比特的H门,可以得到剩下一半的差。

另外一个获得所有边界值的方法是在图像编码过程中使用一个附加量子比特,以2量子比特图像状态为例:

量子图像处理及其应用:边缘检测(五)-量子客

具体过程如下:

  1. 增加一个额外的量子比特,对图像状态进行冗余编码,如图中第二列所示。
  2. 将H门作用在图像状态的最后一个量子比特上,可以得到图中第三列图示,即两个相邻像素的求和/差。
  3. 对图像状态的最后一个量子比特测量,当结果为1时,可以得到图中最右侧状态。这个输出状态就包含了全部的边界信息。

【综上】通过沿着不同方向的图像编码,相关的边界信息可以被检测到,例如行/列扫描得到垂直/水平边界。

  1. 这个quantum Hadamard edge detection (QHED)算法产生了一个编码边界信息的量子态。将这个量子态转换为经典的信息需要进行$O(2^n)$次测量。
  2. 但是如果我们的目标是比如:判断在图片中是否存在一个特殊的模式,就可能只需要执行一次本地测量操作即可。
  3. 一个好的示例是swap test能够判断一个输出图像和相关图像的相似性(如附录D)。

QHED算法数值分析

作为数值示例,下图显示了QHED算法在经典计算机上模拟的输出。该示例的输入是一个二进制(b/w)图像F_cat。

量子图像处理及其应用:边缘检测(五)-量子客
QHED算法的数值模式,图(a)表示256*256的输入图像;图(b)表示编码边界信息的输出图像。通过概率幅值0和1分别编码白色像素和黑色像素。

对于这个简单的示例,文献[1]仅采用了二元图像(QHED算法对一般的灰度图像也是有效的)。

  1. 一个256*256的图像F_cat通过16量子比特的量子态|f_cat〉进行编码(在经典编码中,需要$2^{16}=65536$经典比特,即8kB)。
  2. 此后,对量子态|f_cat〉执行酉操作$I_{2^{15}}\bigotimes{H}$。
  3. 最终通过输出状态解码得到的图像信息可以看出,QHED算法能够成功的检测到图像的边界。

QHED算法实验验证

为了实验性测试QHED算法,在4比特量子寄存器通过量子态$\mid{f_e}\rangle$编码了一个简单的图像:

$F_e=\frac{1}{2\sqrt{2}}\left[\begin{array}{cccc}0&1&0&0\\1&1&1&0 \\1&1&1&1\\0&0&0&0\end{array} \right ]$

此后,对最后一个量子比特执行一个单量子比特的H门,并保证其他量子比特不被改变,即

$\hat{U_e}=I_8\bigotimes{H}$。

此时,将产生输出态$\mid{g_e}\rangle=\hat{U_e}\mid{f_e}\rangle$中一半像素的边界信息(偶数位置),并可以通过实验谱分析读出相关结果。

文献[1]分别执行了两次实验来获得奇数和偶数位置的边界信息:

  • 对于奇数位:采用了概率幅置换操作;
  • 对于偶数位:无需采用概率幅置换操作。

为了测试执行结果的正确性,文献[1]测量了输入和输出图像状态并得到它们的保真度范围为[0.972,0.981]。

边界信息的实验结果如下图所示。与理论数据相比,实验的输入和输出图像的欧式距离分别是0.06和0.08。

量子图像处理及其应用:边缘检测(五)-量子客

该图显示了QHED算法的实验结果。

  • 顶部蓝色曲线表示的是$^{13}C$的谱:图(a)是输入图像$F_e$,图(b)是输出图像标记边界信息;红色曲线表示的是模拟的部分,为了方便清晰的识别,对红色曲线进行了移动。
  • 在图(a)中,谱概率幅被放大了1.8倍;
  • 在图(b)中,顶部(底部)的频谱是对$\mid{f_e}\rangle\mid{f‘_e}\rangle)$执行一次H门的结果。
  • $^{13}C$的频谱通过执行π/2脉冲得到。
  • 最底部的两个平面分别表示(c)输入的4*4图像和(d)输出的标明边界信息的图像排列。其中,3D柱形图(顶部)显示了图像的概率幅值;2D视觉平面图中的每一个方形表示一个像素。

小结

关于文献[1]的解读,暂时就告一段落。这篇文献主要展示了量子算法在图像处理中能够发挥的潜能。也欢迎对这个领域感兴趣的朋友来约稿一起分享所学所得。下期见~

[1] Yao X W, Wang H, Liao Z, et al. Quantum Image Processing and Its Application to Edge Detection: Theory and Experiment[J]. Physical Review X, 2017, 7(3).

[2] Y. Zhang, K. Lu, and Y. Gao, Qsobel: A Novel Quantum Image Edge Extraction Algorithm, Sci. China Inf. Sci. 58, 1 (2015).

[3] A. Fijany and C. Williams, in Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications (Springer, Berlin, 1998), pp. 10–33.

注:作者:Duan.Bojia (QubitLab)
编辑:Zoe
校对:量豆豆
本文原创,首发在《量子机器学习》微信公众号,欢迎关注。最后感谢Zoe在量子客对本文的再次整理、校验与编辑。
量子图像处理及其应用:边缘检测(五)-量子客