基于Prewitt算子的量子邊緣檢測算法

郝大鵬，丁 琦

(西安航空學院 理學院，西安 710077)

0 引言

量子算法是以量子力學基本原理設計的，能夠運行在量子計算機上的程序算法[1]。自上世紀90年代Shor算法和Grover算法提出后，量子算法被證實可以有效解決計算機NP問題，克服傳統計算方法所帶來的瓶頸[2]。由于量子疊加性和并行性等內在特點，量子算法可以大幅提高大規模數據處理的速度，是量子計算的研究熱點。

量子圖像處理是量子算法在圖像處理領域的應用[3]。2003年Venegas-Andraca與Bose[4]開創性地提出了利用量子力學存儲、處理和恢復圖像的方法，標志著量子圖像處理的開端，2011年Le提出FRQI(Flexible Representation of Quantum Images)[5]圖像表示方法，可以有效地利用量子算法存取圖像，促使量子圖像處理成為量子算法研究的熱點。圖像表示方法是進一步圖像處理的基礎，近幾年涌現出了大量的量子圖像表示方法，例如，Sun等提出了MCQI(Multi Channel Representation of Quantum Images)彩色圖像表示方法，Zhang等提出了NEQR(novel enhanced quantum representation of digital images)增強圖像表示方法和QUALPI(quantum log-polar image)對數極坐標圖像表示方法[6]，李盼池等提出了改進FRQI圖像表示方法[7]。同時，基于各類量子圖像表示方法的圖像處理方法也逐漸增多，Dang等人在2017年提出了量子圖像匹配算法[8]，2018年提出了量子圖像分類算法[9]; Wang等人在2018年提出了量子圖像分割方法[10]。Fan等人在2019年提出了基于Laplacian算子的圖像邊緣檢測方法[11]。目前，量子圖像處理方法相比傳統圖像處理而言算法仍然剛剛起步，算法還不夠豐富。

圖像邊緣檢測是圖像預處理的重要內容，是圖像中目標選取以及圖像識別和理解的最基本環節，為了能夠快速高效的檢測圖像邊緣，本文提出基于經典Prewitt算子的量子邊緣檢測方法。提出的算法相比Fan等人提出的Laplacian算子的圖像邊緣檢測方法算法的量子成本更低，更便于在量子集成電路中集成。

1 經典Prewitt算子邊緣檢測方法

Prewitt算子是一階微分算子，基于Prewitt算子的邊緣檢測原理是利用模板與圖像進行鄰域卷積運算，其中模板算子為兩個3×3的矩陣，分別從兩個正交方向進行計算圖像各點的灰度變化梯度，當灰度變化值大于閾值時，判定該點為邊緣點，連接圖像中所有的邊緣點即可獲得圖像的邊緣，經典Prewitt算子為[12]：

其中，P為需檢測的圖像，u,v表示圖像水平與垂直方向的位置。

2 提出的量子圖像算法

2.1 量子圖像表示

根據經典Prewitt算子邊緣檢測方法的特點，本文選取Zhang等提出了NEQR圖像表示方法表示，圖1為NEQR表示法的示意圖。

圖1 NEQR表示法的示意圖[6]圖2相鄰位置示意及符號

為了保存圖像中像素點相鄰的8個位置的灰度值及邊緣點標定值，改進的NEQR表示方法，增加9個量子比特位，圖像初始化為：

(3)

其中，?是Kronecker 積，CYX是圖像(x,y)的灰度值，標定值為ΩYX，1表示邊緣點，0表示非邊緣點。存儲灰度值的8個量子比特位置示意如圖2所示。

2.2 移位變換

在計算灰度變化梯度需要獲取像素點相鄰8個點的灰度值，這些相鄰點位置需要利用移位變換來獲得,移位變換本質上是mod2加減法，移位變換表示為：

2.3 邊緣點判定

根據經典Prewitt算子邊緣檢測, ΩYX標定值可以根據式(6)計算并存儲。

其中，T是閾值，Gx(Y,X)和Gy(Y,X)可以根據式(7)(8)獲得。

GY(Y,X)=(CY-1,X-1+CY-1,X+CY-1,X+1)-(CY+1,X-1+CY+1,X+CY+1,X+1)

(7)

GX(Y,X)=(CY-1,X+1+CY,X+1+CY+1,X+1)-(CY-1,X-1+CY,X-1+CY+1,X-1)

(8)

2.4 提出方法的量子電路

根據經典Prewitt算子邊緣檢測方法及前述內容，提出方法的量子電路實現如圖3所示。

圖3量子電路圖

3 仿真測試

本文使用python3.7+Qiskit0.10仿真了圖3所示的量子電路，測試圖像為512×512像素的Lena標準灰度測試圖像，測試的邊緣閾值為128，測試結果如圖4所示。

圖4仿真測試結果

從圖(b)可以得出本文提出的量子Prewitt算子邊緣檢測算法是有效的，從圖(c)可以得出算法可以恢復到原始圖像，保證了量子算法的可逆性。

4 結論

本文提出來的算法的量子成本(quantum cost)為2n+8+8+1量子比特，其中2n個量子比特存儲圖像信息，8量子比特保存圖像的灰度值，8個量子比特保存Prewitt算子計算的鄰居位置的灰度值，1個量子比特保存標定值，參考文獻[11]的量子成本為2n+q+8，其中q為控制位，依文中所述，q=n，故而從量子成本上本文提出的算法量子成本更低。根據參考文獻[13],計算簡便的Prewitt邊緣檢測方法更便于硬件的實現。