經(jīng)典Canny 邊緣檢測(cè)的量子實(shí)現(xiàn)

鮑華良趙 婭

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,黑龍江 大慶163318)

0 引 言

量子圖像處理是量子計(jì)算和圖像處理的新興交叉學(xué)科,2003年,Beach等[1]首次報(bào)道了有關(guān)量子圖像處理的研究。進(jìn)行量子圖像處理的第1步是將經(jīng)典圖像用量子方法表示。早期提出的兩個(gè)轉(zhuǎn)換模型是量子比特晶格表示法[2]和實(shí)矢量表示法[3]。盡管這兩種表示法都有一些缺陷,但它們?yōu)楹罄m(xù)研究奠定了基礎(chǔ)。量子圖像處理的快速發(fā)展得益于2011年Le等[4]提出的FRQI(Flexible Representation of Quantum Images)表示法,該模型首次使用量子疊加態(tài)存儲(chǔ)像素的位置。之后提出的表示模型都是其基本模型的修改或擴(kuò)展,如SQR(Simple Quantum Representation)[5]、MCQI(Multi-Channel Quantum Images)[6-7]等。2013年,Zhang等[8]提出了新型的數(shù)字圖像增強(qiáng)量子表示法(NEQR:Novel Enhanced Quantum Representation),這種表示方法的優(yōu)點(diǎn)是,通過有限次數(shù)的投影測(cè)量,可以精確地檢索出像素的顏色信息。

目前,量子圖像處理已經(jīng)開展的工作主要包括:圖像置亂[9-10]、圖像加密[11]、圖像水印[12-13]、圖像隱寫[14]、量子電影[15]、量子音頻[16]、圖像匹配[17-18]、圖像分割[19-23]、幾何變換[20]、顏色處理[21]、特征提取[22]、圖像定位[24]和邊緣檢測(cè)[25-26]。經(jīng)典圖像處理中,邊緣檢測(cè)涉及卷積或相關(guān)計(jì)算,而使用量子線路實(shí)現(xiàn)這些計(jì)算是相對(duì)困難的。Fan等[27-28]提出了基于Laplacian算子和零交叉方法的量子圖像邊緣提取,同時(shí)提出了基于經(jīng)典Sobel算子的NEQR的量子圖像邊緣提取。文獻(xiàn)[27-28]作為量子邊緣檢測(cè)的先驅(qū),對(duì)未來的研究具有指導(dǎo)意義。

綜上所述,量子圖像處理經(jīng)過十多年的發(fā)展,已經(jīng)取得了許多原創(chuàng)性的成果,但仍面臨許多挑戰(zhàn)[29]。例如,在經(jīng)典圖像處理中,邊緣檢測(cè)方法非常完備,但對(duì)量子圖像處理還不成熟。筆者研究了基于量子計(jì)算的Canny邊緣檢測(cè)的實(shí)現(xiàn)方案,設(shè)計(jì)了完整的量子線路。借助量子計(jì)算的并行性,該方案可以實(shí)現(xiàn)對(duì)應(yīng)經(jīng)典方案的指數(shù)加速,經(jīng)典計(jì)算機(jī)上的仿真驗(yàn)證了方案的正確性。

1 預(yù)備知識(shí)

1.1 經(jīng)典Canny邊緣檢測(cè)

令f(x,y)表示輸入圖像,G(x,y)=e-(x2+y2)/(2σ2)是高斯濾波函數(shù)。Canny邊緣檢測(cè)算法包括如下步驟。

Step 1 用高斯濾波器平滑輸入圖像得到fs(x,y)。

Step 2 采用Sobel算子計(jì)算梯度的幅值圖像和角度圖像

Step 3 對(duì)梯度幅值圖像應(yīng)用非最大抑制。

對(duì)以α(x,y)中每個(gè)(x,y)為中心的3×3區(qū)域,應(yīng)用Rafael等[30]提出的非最大值抑制方案:首先找出最接近α(x,y)的方向dk。若M(x,y)沿dk方向大于其鄰近的兩個(gè)像素值,則令gN(x,y)=M(x,y),否則gN(x,y)=0,此時(shí)gN(x,y)即為非最大抑制圖像。

Step 4 采用雙閾值處理檢測(cè)并連接邊緣。

Canny算法通過使用兩個(gè)閾值改進(jìn)該狀況。設(shè)置高閾值為TH,低閾值為TL。通常高閾值和低閾值的比率可取為2 ∶1或3 ∶1。雙閾值處理操作視為

兩幅閾值圖像的疊加。起始gNH(x,y)和gNL(x,y)都被置為零,但由于gNL(x,y)是使用低閾值形成的,故在閾值處理后gNH(x,y)的非零像素通常少于gNL(x,y),且gNL(x,y)中包含著gNH(x,y)中所有非零的像素。通過令

從gNL(x,y)中刪除所有來自gNH(x,y)的非零像素點(diǎn)。gNH(x,y)中的邊緣通常會(huì)存在縫隙,可使用文獻(xiàn)[26]中的方法形成較長(zhǎng)的邊緣。最后,將gNL(x,y)中所有的非零像素附加到gNH(x,y)中,此時(shí)即可得到Canny邊緣檢測(cè)圖像。

1.2 NEQR模型

考慮到Canny邊緣檢測(cè)涉及大量的灰度值計(jì)算,所以采用NEQR模型表示量子圖像。對(duì)一幅2n×2n且顏色值范圍均為{0,1,…,2q-1}的灰度圖像,NEQR可描述為

1.3 補(bǔ)碼定義

在Canny邊緣檢測(cè)中,由于梯度值可能為負(fù)數(shù),為方便計(jì)算,像素的灰度值統(tǒng)一用二進(jìn)制補(bǔ)碼表示,為此首先給出二進(jìn)制補(bǔ)碼的定義。

設(shè)x為一個(gè)n+1位的二進(jìn)制數(shù),包括1個(gè)符號(hào)位(0表示“+”,1表示“-”),m個(gè)整數(shù)位,以及n-m個(gè)小數(shù)位。x的補(bǔ)碼

獲得。在后面設(shè)計(jì)的各種模塊中,所有與像素的灰度值有關(guān)的數(shù)據(jù)都將用二進(jìn)制補(bǔ)碼表示。

1.4 量子比較器

量子比較器的設(shè)計(jì)方法可參見文獻(xiàn)[27],為便于描述,采用圖2 a給出的模塊符號(hào)圖表示,其中x和y是兩個(gè)n比特輸入數(shù),e1e0是輸出比特。若e1e0=10,則x＞y;若e1e0=01,則x＜y;若e1e0=00,則x=y。

1.5 模加1和模減1

對(duì)n位無符號(hào)整數(shù)x,這兩個(gè)模塊分別實(shí)現(xiàn)模加1和模減1。對(duì)n+1位有符號(hào)數(shù),這兩個(gè)模塊分別實(shí)現(xiàn)x+2m-nmod 2m和x-2m-nmod 2m。兩模塊的符號(hào)如圖2 b、圖2 c所示,具體量子線路設(shè)計(jì)參見文獻(xiàn)[22]。

圖2 比較器、模加1和模減1量子線路的模塊符號(hào)Fig.2 Module symbols of quantum circuits of comparator,modulo plus 1 and minus 1

2 量子Canny邊緣檢測(cè)的線路設(shè)計(jì)

2.1 一些輔助模塊的量子線路

1)復(fù)制模塊。該模塊的功能是將一個(gè)n比特量子態(tài)復(fù)制到另一個(gè)n比特量子態(tài)顯然可以用n個(gè)受控非門實(shí)現(xiàn)。具體的量子電線如圖3所示。在該模塊的符號(hào)中,不變的輸入和輸出用實(shí)心條標(biāo)注。

圖3 復(fù)制模塊量子線路圖Fig.3 The quantum circuit of copy module

2)翻轉(zhuǎn)加1模塊。該模塊計(jì)算n+1位有符號(hào)數(shù)的相反數(shù)。設(shè)x=xm,xm-1…x0.x-1…xm-n為n+1位有符號(hào)數(shù),該模塊首先對(duì)x中的所有量子比特進(jìn)行翻轉(zhuǎn),然后對(duì)翻轉(zhuǎn)后的量子比特實(shí)施模加1,量子線路如圖4所示。

圖4 翻轉(zhuǎn)加1模塊量子線路圖Fig.4 The quantum circuit of flip and plus 1

3)左移和右移模塊。左移模塊將有符數(shù)x=xm,xm-1…x0.x-1…xm-n依次向左移動(dòng)1個(gè)比特位,并將最低有效位置為0,如下所示

該模塊也稱加倍模塊。其具體的量子線路如圖5所示。該模塊將在設(shè)計(jì)補(bǔ)碼除法器中發(fā)揮重要作用。

圖5 左移模塊量子線路圖Fig.5 The quantum circuit of left shift module

右移模塊將有符數(shù)x=xm,xm-1…x0.x-1…xm-n依次向右移動(dòng)1個(gè)比特位,使其成為n+2位的有符號(hào)數(shù)。由

可知,右移模塊將數(shù)值減半,其量子線路如圖6所示。

圖6 右移模塊量子線路圖Fig.6 The quantum circuit of right shift module

4)絕對(duì)值模塊。該模塊計(jì)算有符號(hào)數(shù)x=xm,xm-1…x0.x-1…xm-n的絕對(duì)值,其量子線路如圖7所示。

圖7 絕對(duì)值模塊量子線路圖Fig.7 The quantum circuit of absolute value

5)模加法器模塊。加法包括模加法和非模加法,如果加法的結(jié)果小于模,則這兩種加法是等價(jià)的。對(duì)兩個(gè)n+1位有符號(hào)數(shù)的加法,如果結(jié)果超過模,則通過使用n+2位表示這兩個(gè)數(shù),這兩個(gè)加法仍然是等價(jià)的。設(shè)兩個(gè)有符號(hào)數(shù)分別為x=xm,xm-1…x0.x-1…xm-n,y=ym,ym-1…y0.y-1…ym-n,且2m-1。模加法器的量子線路圖如圖8所示。

圖8 量子模加法器模塊量子線路圖Fig.8 The quantum circuits of modulo adder

6)補(bǔ)碼比較器模塊。圖2a中的比較器只能比較兩個(gè)無符號(hào)整數(shù),對(duì)兩個(gè)n+1位有符號(hào)數(shù)的比較,可使用圖9所示的補(bǔ)碼比較器實(shí)現(xiàn)。

圖9 補(bǔ)碼比較器模塊量子線路圖Fig.9 The quantum circuit of complement comparator

7)補(bǔ)碼乘法器模塊。設(shè)x=xm,xm-1…x0.x-1…xm-n,y=ym,ym-1…y0.y-1…ym-n為2個(gè)n+1位有符號(hào)數(shù)的補(bǔ)碼,實(shí)現(xiàn)x×y的量子線路如圖10所示。在這個(gè)線路中,乘積采用2n+1個(gè)比特描述,包括1個(gè)符號(hào)位、2m個(gè)整數(shù)位和2(n-m)個(gè)小數(shù)位。

圖1 一個(gè)平滑圖像fs的3×3區(qū)域和Sobel算子Fig.1 A 3×3 region of smoothed image fs and two Sobel operaters in X and Y directions

圖10 兩個(gè)有符號(hào)數(shù)補(bǔ)碼乘法器的量子線路圖Fig.10 The quantum circuit of complement multiplier for two signed numbers

此時(shí),兩個(gè)任意有符號(hào)數(shù)x和y的商可由

計(jì)算。顯然式(11)涉及指數(shù)計(jì)算,p是m+1位有符號(hào)數(shù)的補(bǔ)碼表示,其中p=pm,pm-1…p0,需要解決在x和p都已知的情況下計(jì)算2p x,實(shí)現(xiàn)此功能的量子線路如圖13所示。

圖13 已知x,p計(jì)算2p x的量子線路圖Fig.13 The quantum circuit for caculating 2p x based on known x and p

綜上所述,筆者設(shè)計(jì)的任意兩個(gè)有符號(hào)數(shù)的補(bǔ)碼除法器的量子線路如圖14所示。該模塊將用于量子Canny邊緣檢測(cè)的梯度角度圖像。

圖14 實(shí)現(xiàn)任意兩個(gè)有符號(hào)數(shù)補(bǔ)碼除法的量子線路圖Fig.14 The quantum circuit of complement division for any two signed numbers

2.2 實(shí)現(xiàn)Canny邊緣檢測(cè)的量子線路

1)原始圖像的高斯濾波。為避免卷積運(yùn)算,采用移位、堆疊、加權(quán)求和的方法實(shí)現(xiàn)輸入圖像的高斯濾波。先將原始圖像在8個(gè)方向(即上左、上、上右、左、右、下左、下、下右)移位一個(gè)單位或多個(gè)單位(取決于濾波器模板的大小)。然后將移位后的圖像和原始圖像按照固定的順序進(jìn)行堆疊。在這些堆疊的圖像中,相同位置的像素就是原始圖像中被濾波器模板覆蓋的像素。最后,以濾波器模板中的對(duì)應(yīng)的值為權(quán)重,計(jì)算這些位置相同的像素的加權(quán)和就是原始圖像中相應(yīng)像素的濾波結(jié)果。這種方法的優(yōu)點(diǎn)是,借助量子計(jì)算的并行性,可以同時(shí)處理疊加圖像中相同位置的所有像素。

實(shí)現(xiàn)高斯濾波的第1步是確定濾波器的大小。筆者采用文獻(xiàn)[28]提出的方法,即濾波模板邊長(zhǎng)S通常取大于6σ的最小的正奇數(shù),其中σ為輸入圖像短邊長(zhǎng)度的0.5%。本文中,當(dāng)輸入圖像的短邊長(zhǎng)度小于300時(shí),采用上述方法確定S,否則,取S=9,σ=1.5。在確定高斯濾波器的大小后,通過對(duì)高斯函數(shù)進(jìn)行采樣,可得到高斯濾波器模板。以128×128像素的輸入圖像為例,σ=0.64,「6σ]=4,S=5,此時(shí)采樣得到的高斯濾波器模板如圖15a所示。設(shè)輸入圖像為Ixy,根據(jù)移位、堆疊、加權(quán)求和,此時(shí),需要生成24幅移位圖像,如圖15b所示。

圖15 一個(gè)5×5的高斯濾波器模板和對(duì)應(yīng)輸入圖像在所有方向上的轉(zhuǎn)換Fig.15 A 5×5 Gaussian filtering mask and its corresponding input image translation in all directions

筆者以3×3的濾波器模板為例,設(shè)計(jì)了實(shí)現(xiàn)高斯濾波的量子線路,如圖16所示。其中像素的輸入圖像,灰度值由n+1位有符號(hào)數(shù)的二進(jìn)制補(bǔ)碼表示,包括一個(gè)符號(hào)比特和n個(gè)數(shù)據(jù)比特,整個(gè)線路可分為3部分。

圖16 高斯濾波量子線路圖Fig.16 The quantum circuit of Gaussian filtering

第1部分如第1個(gè)虛線框中的線路所示,用于生成與輸入圖像完全相同的8幅空?qǐng)D像。然后利用若干比較器和復(fù)制模塊將輸入圖像的灰度值復(fù)制給這8幅空?qǐng)D像。第2部分如第2個(gè)虛線框中的線路所示,用于獲得向各方向的平移圖像。第3部分如第3個(gè)虛線框中的線路所示,用于計(jì)算堆疊圖像中相同位置的加權(quán)和,即濾波結(jié)果。為使計(jì)算結(jié)果盡可能精確,對(duì)所有結(jié)果保留小數(shù)點(diǎn)后4位,即精確到

0.000 1,由2-14＜10-4,二進(jìn)制小數(shù)需要用14個(gè)量子位表示,灰度范圍0~255需要用8個(gè)量子位表示,因此總共需要1+8+14=23量子位。

為獲得梯度幅值圖像和角度圖像,需要利用式(1)和式(2)計(jì)算經(jīng)過Sobel算子處理后輸出的梯度幅值和角度。為簡(jiǎn)化量子線路設(shè)計(jì),利用

代替式(1)和式(2)。式(12),式(13)利用絕對(duì)值代替平方和開方運(yùn)算,使用正切值代替角度值。這種簡(jiǎn)化有效避免了復(fù)雜的量子線路設(shè)計(jì)。后續(xù)的實(shí)驗(yàn)結(jié)果表明這種簡(jiǎn)化對(duì)邊緣檢測(cè)的結(jié)果沒有影響。

簡(jiǎn)化公式只涉及加法和除法運(yùn)算,從而簡(jiǎn)化了量子線路設(shè)計(jì),只需比較gx和gy的像素位置,當(dāng)位置相同時(shí),進(jìn)行兩個(gè)像素值的加法和除法,并將計(jì)算結(jié)果復(fù)制到空?qǐng)D像中相同位置的灰度值。具體量子線路圖如圖18所示分別是梯度幅值圖像和梯度角度正切值圖像。

圖18 計(jì)算梯度幅值和角度正切值的量子線路圖Fig.18 The quantum circuit of computing gradient magnitude and tangent of gradient angle

3)對(duì)梯度幅值圖像的非最大抑制。與經(jīng)典的Canny邊緣檢測(cè)類似,對(duì)梯度幅值圖像的非最大抑制要分別在4個(gè)方向上實(shí)現(xiàn),因此需要預(yù)先確定4個(gè)方向上的梯度角度的正切值的范圍。通過對(duì)單位圓8等分可知,水平、垂直、+45°、-45°的4個(gè)方向的正切值范圍如下

其中t1=-0.414 2,t2=0.414 2,t3=2.414 2,t4=-2.414 2。實(shí)現(xiàn)水平方向非最大抑制的量子線路如圖19所示,其他方向的量子線路設(shè)計(jì)與之類似,不再贅述。

圖19 水平方向非最大抑制的量子線路圖Fig.19 The quantum circuit for non-maxima suppression in horizontal direction

圖19中黑色虛線右側(cè)的線路使用絕對(duì)值模塊和量子比較器模塊判斷正切值是否滿足水平邊緣的條件。若當(dāng)前正切值滿足水平邊緣條件,且滿足條件Mag(p)＞max(I12(p),I32(p)),則將Mag(p)的結(jié)果存儲(chǔ)到的當(dāng)前位置。

4)基于雙閾值的邊緣細(xì)化和連接。

圖21 Canny邊緣檢測(cè)的量子線路的總體框架圖Fig.21 The general framework of quantum circuit for Canny edge detection

相比文獻(xiàn)[26]中的Canny邊緣檢測(cè)量子實(shí)現(xiàn),筆者使用的濾波器模板大小不是固定的,而是隨輸入圖像大小自適應(yīng)變化,且濾波器模板中的數(shù)值是經(jīng)典連續(xù)濾波函數(shù)的采樣結(jié)果,這樣的設(shè)計(jì)與經(jīng)典Canny邊緣檢測(cè)的效果更為接近。

2.3 復(fù)雜度分析

為便于描述,以一個(gè)2k×2k像素的灰度圖像(共2 k+23個(gè)比特)為例,分析模型的線路復(fù)雜度。在量子圖像處理中,模型復(fù)雜度取決于線路中基本門(大小為2×2的酉算子)數(shù)量,且基本門的復(fù)雜度默認(rèn)為1[32]。下面通過分析各子模塊的復(fù)雜度,逐步得出整個(gè)模型的線路復(fù)雜度。

從文獻(xiàn)[31]可知,模加1和模減1模塊、比較器模塊的復(fù)雜度都不超過O(k2)。從圖3~圖5可知,復(fù)制模塊由n個(gè)受控非門組成,因此復(fù)雜度為O(n)。翻轉(zhuǎn)加1模塊由n個(gè)非門和1個(gè)模加1模塊組成,因此復(fù)雜度是O(n2+n)≈O(n2)。左移模塊由n個(gè)交換門和兩個(gè)受控非門組成。每個(gè)交換門可以分解為3個(gè)受控非門,所以電路的復(fù)雜度為O(3 n+2)≈O(n)。同理,右移模塊的復(fù)雜度也是O(n)。

從圖7和圖8可知,絕對(duì)值模塊由一個(gè)受控非門和一個(gè)翻轉(zhuǎn)加1模塊組成,因此復(fù)雜度約為O(n2+1)≈O(n2)。模加法器包括2 n個(gè)進(jìn)位模塊和n+1個(gè)求和模塊。每個(gè)進(jìn)位模塊由2個(gè)Toffoli門和1個(gè)受控非門組成,每個(gè)求和模塊由2個(gè)受控非門組成。根據(jù)文獻(xiàn)[32],1個(gè)Toffoli門可以近似為6個(gè)受控非門,因此模加法器的復(fù)雜度為O(28 n+2)≈O(n)。

根據(jù)圖9和圖10可知,補(bǔ)碼比較器模塊由1個(gè)模加法器、1個(gè)翻轉(zhuǎn)加1模塊、1個(gè)非門和1個(gè)受控非門組成。因此,復(fù)雜度不超過O(n2+n+2)≈O(n2)。補(bǔ)碼乘法器由2(n+1)個(gè)模加法器、2 n+1個(gè)翻轉(zhuǎn)加1模塊以及n個(gè)右移模塊組成,補(bǔ)碼乘法器的復(fù)雜度為O((2 n+1)n+(2 n+1)n2+n2),即O(n3)。

由圖11~圖13可知,補(bǔ)碼除法器包括預(yù)處理、除法器、2px等模塊。如圖12所示,預(yù)處理模塊由翻轉(zhuǎn)加1、左移模塊、右移模塊、模加1和模減1模塊組成,其復(fù)雜度不超過O(k2+n2)。由文獻(xiàn)[33]和文獻(xiàn)[34]可知,除法器的復(fù)雜度不超過O(n3)。2px模塊由左移,右移、模加1、模減1模塊組成,其復(fù)雜度不超過O(k2+n)。所以補(bǔ)碼除法器的復(fù)雜度不超過O(k2+n3)。對(duì)大小為S×S的高斯濾波器模板,線路包含2(S2-1)k個(gè)Hadamard門、4(S2-1)個(gè)比較器,0.5(S3-S)個(gè)模加1和模減1模塊、S2-1個(gè)復(fù)制模塊、S2-1個(gè)補(bǔ)碼乘法器和S2-1個(gè)模加法器。因此,高斯濾波器線路的復(fù)雜度過O(k2)。

圖12 對(duì)有符號(hào)數(shù)x進(jìn)行預(yù)處理的量子線路圖Fig.12 The quantum circuit of preprocessing for a signed number x

根據(jù)圖17可知,Sobel-X和Sobel-Y由比較、復(fù)制、左移、模加1模減1、翻轉(zhuǎn)加1、模加法器組成。因此,它們的復(fù)雜度不超過O(k2+n2)。梯度幅值模塊由比較器、復(fù)制、補(bǔ)碼比較器和模加法器組成,因此復(fù)雜度不超過O(k2+n3)。梯度角度模塊主要由比較器和量子除法器組成。因此其復(fù)雜度不超過O(k2+n3)。從圖19和圖20可知,非極大抑制模塊主要包括比較器、復(fù)制、量子比較器模塊。因此,復(fù)雜度不超過O(k2+n2)。雙閾值模塊主要由比較器、復(fù)制模塊、補(bǔ)碼比較器、模加1和模減1以及模加法器模塊組成。因此,復(fù)雜度不超過O(k2+n2)。

圖17 Sobel-X算子及對(duì)應(yīng)的量子線路圖Fig.17 Sobel-X mask and its quantum circuit

圖20 基于雙閾值的邊緣細(xì)化和連接的量子線路圖Fig.20 The quantum circuit for edge refinement and linking based on double threshold

綜上所述,筆者設(shè)計(jì)的邊緣檢測(cè)方案的復(fù)雜度為O(k2+8(k2+n2)+(k2+n3))≈O(k2+n3)。

3 仿真結(jié)果及分析

由于目前量子計(jì)算機(jī)的硬件實(shí)現(xiàn)尚處于理論探索階段,所以仿真只能在經(jīng)典計(jì)算機(jī)上進(jìn)行。雖然不能驗(yàn)證量子計(jì)算的并行性,但能驗(yàn)證方案的執(zhí)行效果。所有仿真在配置為英特爾(R)Core(TM)i7-10700CPU@2.90 GHz、8.00 GByte內(nèi)存和64位操作系統(tǒng)的臺(tái)式機(jī)上進(jìn)行,軟件采用Matlab(R2014b)。仿真實(shí)驗(yàn)中用向量表示圖像,用矩陣表示算子,使用的4幅灰度圖像如圖22所示。第1幅為233×233像素,接下來兩幅為512×512像素,最后一幅為1 024×1 024像素。值得指出的是,圖像均采用NEQR模型表示,圖像大小必須滿足2n×2n像素。為使第1幅圖像滿足此要求,分別在圖像底部和右側(cè)增加23行和23列,將圖像擴(kuò)展為256×256像素,并將新增加的像素值全部設(shè)置為零。

圖22 實(shí)驗(yàn)中采用的4幅原始圖像Fig.22 Four original images used in the experiment

對(duì)第1幅233×233像素的圖像,高斯函數(shù)的標(biāo)準(zhǔn)差σ=233×0.5%=1.650,高斯濾波器模板的邊緣長(zhǎng)度為S=「6σ]=7。對(duì)后兩張圖像,因?yàn)閳D像的邊緣長(zhǎng)度大于300,所以σ=1.5,S=9。兩個(gè)濾波器模板中每個(gè)元素的具體數(shù)值分別如圖23a,圖23b所示。

圖23 實(shí)驗(yàn)中使用的兩個(gè)高斯濾波器模板Fig.23 Two Gaussian filtering masks in the experiment

為突出量子Canny邊緣檢測(cè)方案的處理效果,將其結(jié)果與經(jīng)典的Canny邊緣檢測(cè)結(jié)果進(jìn)行了比較。在雙閾值處理中,高閾值和低閾值分別取梯度最大值的30%和10%。量子Canny邊緣檢測(cè)的效果和經(jīng)典Canny邊緣檢測(cè)的效果如圖24a,圖24b所示。

圖24 兩種檢測(cè)方案的實(shí)際效果比較Fig.24 Comparison of the actual effects of two edge detection schemes

上述經(jīng)典計(jì)算機(jī)實(shí)驗(yàn)不能模擬量子計(jì)算的并行性,仿真結(jié)果與用量子計(jì)算機(jī)實(shí)驗(yàn)不完全一致,但可大致模擬量子邊緣檢測(cè)的執(zhí)行結(jié)果。從兩種邊緣檢測(cè)的結(jié)果可以看出,量子方案略優(yōu)于經(jīng)典方案。從圖24可以看出,量子邊緣檢測(cè)方法檢測(cè)到的邊緣更薄而且邊緣周圍的區(qū)域更加清晰。而經(jīng)典方案檢測(cè)到的邊緣更加粗糙,且在邊緣內(nèi)部還有一些模糊區(qū)域。

該實(shí)驗(yàn)中量子Canny邊緣檢測(cè)比經(jīng)典的Canny邊緣檢測(cè)效果略勝一籌,是因?yàn)樵搶?shí)驗(yàn)中高斯濾波使用了不同的濾波器模板。經(jīng)典方案是基于固定的5×5的高斯濾波器模板,而量子方案使用的濾波大小隨輸入的圖像大小而改變。此外,兩種方案的濾波器模板的值也不同,在本實(shí)驗(yàn)?zāi)M經(jīng)典方案時(shí),濾波器模板中的所有數(shù)據(jù)都是整數(shù),并不是用高斯函數(shù)直接采樣的結(jié)果。而量子方案中的濾波器模板的數(shù)據(jù)則是通過高斯函數(shù)直接采樣的結(jié)果。

另外,盡管在經(jīng)典方法中,也可以采用不同大小的濾波器模板,而且濾波器的具體數(shù)值也可以采樣于高斯連續(xù)函數(shù),但兩種方案對(duì)圖像邊界像素的處理方式是不同的。在經(jīng)典方案中,當(dāng)濾波器移動(dòng)到邊界時(shí),對(duì)邊界之外的像素,其像素值一般按0值處理,或采用將邊界像素復(fù)制外推的方式處理;在該方案中,所有邊界像素實(shí)際上都是采用循環(huán)移位的方式處理的,這種方式顯然比經(jīng)典方式中的0值處理方式優(yōu)越。

值得指出,稍好的檢測(cè)效果并不是本方案的核心優(yōu)勢(shì),量子邊緣檢測(cè)方案的核心優(yōu)勢(shì)在于計(jì)算效率的大幅度提升。對(duì)一個(gè)2n×2n像素的圖像,經(jīng)典方案必須逐個(gè)像素執(zhí)行,復(fù)雜度必然含有因子2n,而本方法利用量子計(jì)算的并行性可對(duì)所有像素同時(shí)執(zhí)行濾波操作,在一定程度上實(shí)現(xiàn)了經(jīng)典方案的指數(shù)加速,這是量子方案相較于經(jīng)典方案的核心優(yōu)勢(shì)。

4 結(jié) 語

邊緣檢測(cè)是圖像處理和計(jì)算機(jī)視覺中的一個(gè)基本問題,目的在于識(shí)別數(shù)字圖像中亮度變化顯著的點(diǎn)。在經(jīng)典的方法中,Canny邊緣檢測(cè)的高斯濾波可以通過卷積實(shí)現(xiàn)。筆者使用移位、堆疊、加權(quán)求和的方法避免了卷積運(yùn)算,該方法為設(shè)計(jì)量子圖像濾波提供了可行性。筆者設(shè)計(jì)了經(jīng)典Canny邊緣檢測(cè)的量子版本,從基本的模塊設(shè)計(jì)入手,給出了完整的Canny邊緣檢測(cè)的完整量子線路。經(jīng)典計(jì)算機(jī)上的仿真實(shí)驗(yàn)驗(yàn)證了所提方案的有效性。就邊緣檢測(cè)的效果而言,量子Canny邊緣檢測(cè)的性能略優(yōu)于經(jīng)典Canny邊緣檢測(cè),但該方案的突出優(yōu)勢(shì)在于它的計(jì)算效率,分析表明該方案可以實(shí)現(xiàn)對(duì)經(jīng)典方案的指數(shù)加速。