經典Marr-Hildreth邊緣檢測的量子實現

鮑華良, 趙 婭

(東北石油大學 計算機與信息技術學院, 黑龍江 大慶 163318)

量子圖像處理是融合數學、 量子計算、 量子信息、 圖像處理等形成的交叉學科[1], 其包括量子圖像描述模型和量子圖像處理算法兩方面. 量子圖像描述模型主要包括量子柵格描述[2-3]、 實矢量(real ket)描述[4]、 靈活的量子圖像描述(flexible representation of quantum images, FRQI)[5]、 新的增強量子圖像描述(a novel enhanced quantum representation, NEQR)[6]、 對數極坐標圖像的量子描述[7]等. 量子圖像處理主要包括圖像置亂[8-9]、 圖像加密[10]、 圖像隱藏[11]、 圖像水印[12-13]、 量子電影[14]、 量子音頻[15]、 圖像匹配[16]、 圖像定位[17]、 幾何變換[18]、 顏色處理[19]、 特征提取[20]、 邊緣提取[21]、 邊緣檢測[22]和圖像分割[23]等. 在量子圖像邊緣檢測方面, 目前文獻報道相對較少.

在經典的邊緣檢測中, 一些算子(如Gauss-Laplace濾波(LoG))涉及大量的有理數乘法運算, 而如何設計這些算子的量子線路目前文獻報道較少. 文獻[24]提出了基于Laplace算子和零交叉法的量子圖像邊緣提取方法, 具有較強的指導意義. 但文獻[24]在下列兩點上有進一步的改進空間： 第一, 因為Laplace算子本質上是一種銳化濾波器, 而不是平滑濾波器, 所以使用Laplace算子對原始圖像進行平滑處理并不理想； 第二, 文獻[24]未給出零交叉提取的算子線路設計方法.

本文研究經典Marr-Hildreth邊緣檢測對應的量子實現方法, 該方法包括兩個核心過程: Gauss-Laplace濾波和零交叉提取. 通過設計這兩個核心過程及若干輔助算子的量子線路, 利用量子計算的并行性, 該方法可實現對經典方法的指數級加速. 經典計算機上的仿真實驗驗證了該方法的有效性.

1 預備知識

1.1 經典Marr-Hildreth邊緣檢測

Marr-Hildreth邊緣檢測是經典圖像邊緣檢測的一種重要方法. 該方法的核心是Gauss-Laplace濾波器2G, 可表示為

(1)

經典圖像處理中的Marr-Hildreth邊緣檢測方法, 先對一張圖像f(x,y)采用LoG濾波器實施卷積, 表示為

g(x,y)=[2G(x,y)]*f(x,y),

(2)

然后尋找g(x,y)的零交叉點, 從而確定f(x,y)的邊緣位置.

在任意像素p處的零交叉表示至少有兩個相鄰像素的符號不同, 共有4種情況需要測試： 左/右、 上/下以及兩個對角線.實施時通常先設置一個閾值, 當且僅當相鄰像素灰度值差的絕對值大于該閾值時, 像素p才為一個零交叉像素.

1.2 NEQR模型

對于一張2n×2n的灰度圖像, NEQR模型采用(2n+q)個量子比特描述, 其中q個量子比特描述像素灰度值, 2n個量子比特描述像素位置, 表示為

(3)

圖1 2×2的灰度圖像及對應的NEQR表示Fig.1 Gray-scale image of 2×2 and its NEQR representation

1.3 補碼定義

LoG濾波罩通過對式(1)采樣生成, 所以采樣數據有符號分數, 為便于運算, 本文采用補碼表示. 下面給出補碼定義.

設x為一個(n+1)位的二進制數, 包括1個符號位(0表示“+”, 1表示“-”),m個整數位xm-1,xm-2,…,x0以及(n-m)個小數位x-1,x-2,…,xm-n.x的補碼[x]c定義為

(4)

(5)

在本文設計的各種模塊中, 所有與像素灰度值有關的數據都將用二進制補碼表示.

1.4 量子比較器

比較器在量子Marr-Hildreth邊緣檢測中具有重要作用, 其用于比較不同圖像之間的像素位置, 具體量子線路可參見文獻[26], 為簡便, 本文采用如圖2(A)所示的模塊符號表示, 其中x和y是兩個nbit輸入數,e1e0是輸出比特.若e1e0=10, 則x>y; 若e1e0=01, 則x

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

1.5 模加1和模減1模塊

本文所用的兩個循環移位模塊, 對于n位無符號整數x, 分別實現模加1和模減1.對(n+1)位的有符號數x=xm,xm-1…x0.x-1…xm-n, 分別實現x+2m-nmod 2m以及x-2m-nmod 2m.這兩個模塊的符號分別如圖2(B)和圖2(C)所示, 具體量子線路設計可參見文獻[27].

2 量子Marr-Hildreth邊緣檢測方法

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

2.1.1 復制模塊

該模塊的功能是將一個nbit量子態復制到另一個nbit量子態|0〉?n, 顯然可以用n個受控非門實現.具體的量子線路如圖3所示.由圖3可見, 在該模塊的符號中, 不變的輸入和輸出用實心條標注.該模塊將用于LoG濾波和零交叉提取.

圖3 復制模塊的量子線路Fig.3 Quantum circuits of copy module

2.1.2 翻轉加1模塊

該模塊計算(n+1)位有符號數的相反數.設x=xm,xm-1…x0.x-1…xm-n為(n+1)位有符號數, 該模塊首先對x中的所有量子比特進行翻轉, 然后對翻轉后的量子比特實施模加1.量子線路如圖4所示.該模塊將用于設計補碼比較器和補碼乘法器.

圖4 翻轉加1模塊的量子線路Fig.4 Quantum circuits of flip and plus 1

2.1.3 右移模塊

該模塊將1個(n+1)位有符數x=xm,xm-1…x0.x-1…xm-n向右移動1個比特位, 使其成為(n+2)位的有符號數:

(6)

由式(6)可知, 該模塊也可稱為減半模塊, 該模塊在兩個有符號數的乘法線路設計中具有重要作用, 其量子線路如圖5所示.

圖5 右移模塊量子線路Fig.5 Quantum circuits of right shift module

2.1.4 絕對值模塊

該模塊計算絕對值|x|, 其中x=xm,xm-1…x0.x-1…xm-n,xm是符號位, 該模塊在零交叉提取中具有重要作用, 其量子線路如圖6所示.

圖6 絕對值模塊量子線路Fig.6 Quantum circuits of absolute value module

2.1.5 模加法器模塊

加法包括模加法和非模加法, 如果加法的結果小于模, 則這兩種加法等價.對于兩個(n+1)位有符號數的加法, 如果加法的結果超過模, 則通過使用(n+2)位表示這兩個數, 這兩個加法仍然等價.設兩個(n+1)位有符號數分別為x=xm,xm-1…x0.x-1…xm-n,y=ym,ym-1…y0.y-1…ym-n, 且|x|<2m-1, |y|<2m-1.模加法量子線路如圖7所示.該模塊在LoG濾波和零交叉提取中具有重要作用.

圖7 量子模加法器的量子線路Fig.7 Quantum circuits of quantum modulo adder

2.1.6 補碼比較器模塊

圖2(A)中的比較器只能比較兩個無符號的整數, 對于兩個(n+1)位有符號數的比較, 可使用補碼比較器, 其量子線路如圖8所示.由圖8可見, 首先, 利用復制模塊將|y〉復制給輔助比特, 并應用翻轉加1模塊將其轉換為|-y〉; 然后, 將|x〉和|-y〉提交給模加法器的輸入, 在其輸出端可得到; 最后, 檢查輔助比特|e〉的狀態, 當e=1時,x≥y, 否則x

圖8 補碼比較器的量子線路Fig.8 Quantum circuits of complement comparator

2.1.7 補碼乘法器模塊

補碼乘法器是以基本的量子加法器等為基礎， 設計快速高效的乘法器具有重要意義[28].設x=xm,xm-1…x0.x-1…xm-n,y=ym,ym-1…y0.y-1…ym-n為兩個(n+1)位有符號數的補碼描述, 實現x×y的量子線路如圖9所示.在該線路中, 乘積采用(2n+1)個比特描述, 包括1個符號位, 2m個整數位和2(n-m)個小數位.該模塊在LoG濾波中具有重要作用.

圖9 兩個有符號數補碼乘法器的量子線路Fig.9 Quantum circuits of complement multiplier for two signed numbers

2.2 Marr-Hildreth邊緣檢測的量子線路設計

與經典的數字圖像處理類似, 量子Marr-Hildreth邊緣檢測包括輸入圖像的LoG濾波和濾波后圖像的零交叉提取兩個步驟.

為避免卷積運算, 本文采用一種稱為“移位、 疊加、 加權求和”的方法對量子圖像進行LoG濾波. 首先, 將輸入的原始圖像在8個方向(即上左、 上、 上右、 左、 右、 下左、 下、 下右)移位一個單位或多個單位(取決于濾波罩的大小); 其次, 將移位后的圖像和原始圖像按照固定的順序進行疊加, 在這些疊加的圖像中, 相同位置的像素即為原始圖像中被濾波罩覆蓋的像素; 最后, 以濾波罩中對應的值為權重, 計算這些位置相同像素的加權和, 該加權和即為原始圖像中相應像素的濾波結果. 這種方法的優點是借助量子計算的并行性, 可同時處理疊加圖像中相同位置的所有像素, 從而達到加速經典計算的目的.

2.2.1 輸入圖像的LoG濾波

圖10 一個5×5的LoG濾波罩及輸入圖像在各方向上的移位Fig.10 LoG filtering mask of 5×5 and input image translation in all directions

根據“移位、 疊加、 加權求和”的原理, 本文以3×3的濾波罩為例, 設計實現LoG濾波的量子線路如圖11所示. 其中|I11〉表示大小為2k×2k的輸入圖像, 灰度值由(n+1)位有符號數的二進制補碼表示, 包括一個符號比特和n個數據比特, 整個線路可分為三部分.

第一部分如第一個虛線框中的線路所示, 用于生成與輸入圖像(即|I11〉)完全相同的8張圖像(即|I12〉,|I13〉,|I21〉,|I22〉,|I23〉,|I31〉,|I32〉,|I33〉).第二部分如第二個虛線框的線路所示, 它將第一部分產生的8張圖像分別向8個方向平移, 該操作采用模加1和模減1模塊實現.第三部分如第三個虛線框中的線路所示, 它將第二部分中生成的8張移位圖像進行疊加, 并進一步計算疊加圖像中相同位置像素的加權和, 從而實現LoG濾波. 首先, 用16個比較器確定堆疊圖像中相同位置的像素, 然后用9個補碼乘法器將每個像素|cij〉(i,j=1,2,3)乘以對應的|bij〉(i,j=1,2,3), 最后通過8個加法器實現加權求和.

圖11 實現LoG濾波的量子線路Fig.11 Quantum circuits for LoG filtering

2.2.2 零交叉提取

與經典方法類似, 量子零交叉提取也考察4個方向.以45°方向的零交叉提取為例, 具體的量子線路如圖12所示, 其余3個方向的量子線路基本相同.下面以圖12中的量子線路為例, 簡述零交叉提取的執行過程.|I22〉(|x22〉,|y22〉,|c22〉)為輸入圖像.

圖12 45°方向的零交叉提取Fig.12 Zero-crossing extraction in 45° direction

其次, 用模加1模塊將圖像|I11〉向右下方分別移動1個單位, 用模減1模塊將圖像|I33〉向左上方分別移動1個單位.此時, 在輸入圖像|I22〉和兩個移位圖像|I11〉和|I33〉中, 同一位置的3個像素恰好是|I22〉輸入圖像中45°方向的3個像素.然后使用補碼比較器比較|I11〉和|I33〉中同一位置的像素灰度值, 如果它們的符號相反, 則使用兩個模加法器進一步計算兩個灰度值之和S.

圖13 Marr-Hildreth邊緣檢測的整體框架Fig.13 General framework for Marr-Hildreth edge detection

2.3 復雜性分析

以下分析都基于一個2k×2k的灰度圖像, 共(2k+23)個比特.在量子圖像處理中, 線路網絡的復雜度取決于所使用的基本門數量[30], 包括非門、 Hadamard門、 受控非門以及任何2×2的酉算子, 且基本量子門的復雜度為1.通過分析各子模塊的復雜度, 逐步得到整個量子線路的復雜度.

在本文設計的所有線路中, 只有比較器、 模加1和模減1模塊對像素位置比特進行操作, 其復雜度取決于圖像的大小.其他模塊工作在灰度值上, 與圖像大小無關.由文獻[26]可知, 量子比較器的復雜度不超過O(k2)； 由文獻[20]可知, 模加1和模減1的復雜度也不超過O(k2).對于大小為S×S的LoG濾波罩, 對應線路包含2(S2-1)k個Hadamard門、 4(S2-1)個比較器, 0.5(S3-S)個模加1和模減1模塊、 (S2-1)個復制模塊、 (S2-1)個補碼乘法器和(S2-1)個模加法器.因此, LoG濾波線路的復雜度不超過O(k2).

由圖12可見, 4個零交叉提取線路中共使用了40個比較器和12個模加1和模減1模塊, 故零交叉提取的復雜度為O(40k2+12k2)=O(k2).因此, 本文設計的量子Marr-Hildreth邊緣檢測方案的復雜度不超過O(k2).對于經典Marr-Hildreth邊緣檢測方案, Gauss-Laplace濾波需要計算逐個像素, 其復雜度顯然不低于O(22k).因此本文方法實現了對經典方法的指數加速.

3 經典計算機上的仿真

由于目前量子計算機的硬件實現尚處于理論探索階段, 所以本文仿真只能在經典計算機上進行. 雖然不能驗證量子計算的并行性, 但能驗證方案的執行效果. 所有仿真均在配置Inter(R)Core(TM)i7-10700CPU@2.90 GHz, 8.00 GB內存和64位操作系統的臺式計算機上進行, 軟件采用MATLAB(R2014b). 實驗使用的4張灰度圖像如圖14所示.

圖14 實驗采用的4張原始圖像Fig.14 Four original images used in experiment

第1張圖片大小為233×233, 第2張和第3張圖片大小為512×512, 最后一張圖片大小為1 024×1 024. 本文中圖像均采用文獻[6]提出的NEQR模型表示, 圖像大小必須滿足2n×2n. 為使第1張圖像滿足此要求, 分別在圖像底部和右側增加23行和23列, 將圖像擴展為256×256, 并將新增加的像素值全部設為零.

圖15 實驗用到的兩個Gauss-Laplace濾波罩Fig.15 Two Gauss-Laplace filtering masks used in experiment

3.1 不同邊緣檢測方案性能對比

為考察量子Marr-Hildreth邊緣檢測的處理效果, 將本文方案與經典方案及文獻[24]中的方案進行對比. 為保證比較結果的公平性, 經典方案也使用圖15所示的兩個濾波罩. 在零交叉提取中, 將最大灰度值的5%設定為3種方案的閾值. 對于4張輸入圖像, 3種方案的邊緣檢測效果對比結果如圖16所示. 由圖16可見, 本文方案和經典方案的結果相似, 肉眼分辨不出差別, 但在文獻[24]方案的檢測結果中, 圖像的邊緣有輕微噪聲. 產生以上實驗結果的原因如下：

圖16 3種檢測方案的實際效果比較Fig.16 Comparison of actual effects of three detection schemes

首先, 比較本文方案和經典方案, 二者檢測原理幾乎相同, 僅在邊界像素的處理方式上略有差異, 本文方案采用“移位和堆疊”方法, 而經典方案采用將邊界像素向外擴展的方法, 即當濾波罩中心位于邊界像素時, 濾波罩內缺失的像素按邊界像素處理. 由于邊界像素的數量遠小于整個圖像的數量, 所以檢測結果的差異肉眼幾乎無法判別.

其次, 本文方案和文獻[24]方案的邊緣檢測原理不同, 在文獻[24]方案中, 首先使用Laplace算子對圖像進行濾波, 然后計算濾波后圖像中每個像素上灰度值的二階差分, 最后在二階差分圖像中尋找零交叉像素. 這兩種方案的區別在于圖像預處理的方法不同, 本文LoG算子是Laplace算子和Gauss算子的組合, Gauss算子的功能是對圖像進行平滑處理, 有助于去除圖像中的高頻噪聲, 獲得更清晰的圖像邊緣. 文獻[24]方案采用具有銳化作用的Laplace算子, 其對去除圖像高頻噪聲意義不大, 因此兩個方案檢測的效果略有不同.

根據上述實驗結果, 量子方案檢測效果與經典方案接近. 但本文方案的主要貢獻不是提高檢測效果, 而是提高計算效率. 利用量子計算固有的并行性, 本文方案能實現對經典方案的指數級加速.

3.2 量子比特翻轉噪聲下的邊緣檢測效果

下面通過在量子圖像中混入量子比特翻轉噪聲, 考察噪聲環境下量子圖像的邊緣檢測效果. 量子比特翻轉噪聲本質上是一種信道噪聲, 是信息在量子信道中傳輸時產生的. 它與經典信道噪聲相似, 即在發送0時收到1, 或在發送1時收到0. 對于在信道中傳輸的量子圖像, 量子比特翻轉噪聲將量子比特的狀態在|0〉和|1〉之間翻轉. 本文實驗將翻轉概率設為0.1, 圖14中4張圖像的噪聲版本與其邊緣檢測效果如圖17所示. 由圖17可見, 雖然噪聲圖像非常模糊, 但邊緣檢測效果在視覺上沒有變化, 表明該方案對噪聲不敏感. 本文方案之所以能抵抗噪聲, 是因為使用的LoG濾波器本質上是Gauss濾波器和Laplace算子的融合, 而Gauss濾波器具有低通平滑的功能, 可在一定程度上濾除混入的噪聲.

圖17 加噪圖像以及對應的邊緣檢測結果Fig.17 Noisy images and corresponding edge detection effects

綜上所述, 本文設計了經典Marr-Hildreth邊緣檢測的量子版本, 給出了實現LoG濾波和零交叉提取的完整量子線路. 經典計算機上的仿真實驗驗證了本文方案的有效性. 盡管該方案在檢測效果上與經典方案差別較小, 但該方案的優勢在于其計算效率. 復雜度分析結果表明, 該方案可實現對經典方案的指數級加速. 此外, 本文方案對量子信道噪聲不敏感, 從而增強了方案的魯棒性.