臧一鳴,朱尚超,魏戰(zhàn)紅,劉志飛,林小竹,孫文韜

(北京石油化工學院信息工程學院,北京 102617)

0 引言

量子計算機利用量子態(tài)的疊加性、相干性和糾纏性等獨特的計算特性,展現(xiàn)了優(yōu)越的存儲和并行計算性能,為計算機的發(fā)展帶來了希望[1]。同時IBM的IBM Q[2]與本源量子的本源量子云等量子云平臺與編程框架為量子計算機的發(fā)展帶來了活力。量子計算的分支-量子圖像處理激起了學者的興趣。量子圖像處理是指利用量子力學特性來存儲、分析及處理圖像數(shù)據(jù),包括圖像表示和量子圖像處理算法。

目前,量子圖像表示模型主要有:Qubit Lattice模型[3],Real Ket模型[4],Entangled Image模型[5],量子圖像的靈活表示(FRQI)模型[6],新型增強量子圖像表示(NEQR)模型[7],量子彩色圖像多通道表示(MCQI)模型[8],新型極坐標變換量子圖像表示(QUALI)模型[9],用角度信息來存儲顏色和坐標的QSMC&QSNC模型[10],任意量子疊加態(tài)的多維量子彩色圖像表示(NAQSS)模型[11],通用量子圖像表示(GQIR)模型[12],新型彩色量子圖像表示(NCQI)模型[13],量子圖像位平面表示(BRQI)模型[14]等。

此外,量子圖像處理算法不斷涌現(xiàn),如幾何變換[15]、特征提取[16]、圖像增強[6]、邊緣提取[17]、圖像置亂[18,19]和形態(tài)學圖像處理[20]都有其對應的量子版本。目前,量子圖像各個方向的研究發(fā)展不均衡,有關量子圖像增強算法的研究成果較少。2015年,Jiang等[12]提出了一種量子圖像偽彩色編碼方法,通過構建顏色映射表將灰度圖像映射成彩色圖像。

本文提出的量子圖像偽彩色編碼方法對熱金屬碼分段函數(shù)進行量子化,并給出了該量子算法的量子線路。該方法的優(yōu)點有:一方面,與經(jīng)典偽彩色算法相比,不僅可以減少存儲資源的占用,而且算法運行時間指數(shù)級降低;另一方面,與現(xiàn)有量子圖像偽彩色編碼方法相比,不需要人為設計顏色映射表并不需要構建與之對應的量子數(shù)據(jù),可以減少量子資源的使用、降低空間復雜度,并且對連續(xù)的灰度值可以產生連續(xù)的彩色。對本文所提量子算法在經(jīng)典計算機上用Matlab2020a進行了仿真實驗,驗證了其有效性。

1 量子圖像的表示

GQIR量子圖像表示模型可以存儲任意大小為M×S的量子圖像,存儲Y坐標信息中的M個數(shù)據(jù)需要m量子比特,存儲X坐標信息中的S個數(shù)據(jù)需要s量子比特,其中m和s分別滿足

所以GQIR在存儲大小為M×S的圖像時需要m+s量子比特來存儲位置信息。其中有效存儲圖像位置信息是M×S,冗余像素位置信息是2m×2s-M×S,如圖1所示,其中白色部分為圖像位置信息,陰影部分為冗余像素位置信息。冗余像素的顏色信息部分始終保持為|0〉。

圖1 GQIR表示模型Fig.1 The representation model of GQIR

GQIR表示模型可表示為

圖2 GQIR模型表示下2×3的灰度圖像Fig.2 Grayscale image of size 2×3 represented by GQIR model

圖2給出了一個2×3的灰度圖像,其GQIR表示為

由(1)、(2)式可知

由(5)式可見,存儲2×3的灰度圖像總共需要3量子比特。而實際上,只有6個像素位置(Y=0/1,X=00/01/10)是有用的,其余兩個像素位置是冗余的。

2 量子圖像偽彩色編碼

2.1 經(jīng)典灰度級-彩色變換法

本研究用到的是熱金屬碼,依據(jù)金屬溫度的變化,主要將圖像顏色分為藍色、紅色和黃色三個部分,其中藍色代表低溫物體、紅色代表中溫物體、黃色代表高溫物體,各部分之間實現(xiàn)線性的顏色過渡。熱金屬碼灰度值與RGB彩色值的對應關系如圖3所示。

圖3 熱金屬碼中灰度值與RGB彩色值的對應關系Fig.3 The corresponding relationship between the gray value and the RGB color value in the hot metal code

2.2 量子減法器模塊QSB

參考經(jīng)典數(shù)字邏輯電路中全減器真值表以及邏輯電路的設計,引入了量子減法器的量子線路模塊QSB,如圖4所示。其中|a〉是被減量子位,|b〉是減量子位,|c0〉是量子借位輸入位,|d〉是差量子位,|c1〉是量子借位輸出位。

圖4 QSB的量子線路設計Fig.4 Quantum circuit design of QSB

2.3 量子圖像偽彩色編碼的算法描述

以熱金屬編碼分段函數(shù)為主要研究對象,設計了量子圖像偽彩色編碼方法,彩虹編碼也可以根據(jù)此編碼方法的原理進行設計。

量子圖像偽彩色編碼的輸入為GQIR表示的量子圖像|I〉,包括量子圖像位置信息|YX〉和顏色信息|CYX〉,存儲|CYX〉需要q量子比特。輸出為偽彩色圖像|J〉,顏色信息為|DYX〉,存儲|DYX〉需要p量子比特。在本算法中q=8,p=24,其中表示紅色,表示綠色,表示藍色。

量子圖像偽彩色編碼算法描述如表1所示,其中輸入為灰度圖像|I〉,輸出為偽彩色圖像|J〉,分別定義為

表1 量子圖像偽彩色編碼的算法描述Table 1 Description of quantum image pseudo color coding algorithm

2.4 量子圖像偽彩色編碼的算法實現(xiàn)

偽彩色圖像的存儲總共需要p量子比特。本算法中p=24,首先初始化24量子比特全部為|0〉態(tài),即

2.4.1 量子R變換器量子線路模塊

在量子R變換器中,定義算子W1

定義算子W2

定義算子W3

量子R變換器量子線路模塊如圖5所示。

圖5 量子R變換器量子線路模塊Fig.5 Quantum circuit module of quantum R converter

2.4.2 量子G變換器量子線路模塊

定義算子W4

定義算子W5

定義算子W6

量子G變換器量子線路模塊如圖6所示。

圖6 量子G變換器量子線路模塊Fig.6 Quantum circuit module of quantum G converter

2.4.3 量子B變換器量子線路模塊

定義算子W7

定義算子W8

定義算子W9

定義算子W10

把目標量子位稱為|f3〉。

定義算子W11

把目標量子位稱為|f4〉。

算子W12為受控6位量子減法器f4-W12,需要調用QSB模塊6次。其中|f4〉為控制位,W12為受控算子,有

為6位量子減法器中第j位的差量子位值(從低位算起,圖7中從左往右數(shù)),具體實現(xiàn)如圖7所示。在中,被減量子位為|0〉,減量子位為借位輸入 (輸出)位為 |c1〉,前一級的借位輸出連接到下一級的借位輸入,最低位即的借位輸入位為|0〉。

圖7 6位量子減法器的實現(xiàn)Fig.7 Realization of 6-bit QSB

量子B變換器量子線路模塊如圖8所示。

圖8 量子B變換器量子線路模塊Fig.8 Quantum circuit module of quantum B converter

2.4.4 量子圖像偽彩色編碼量子線路總體設計

算子W1～W3實現(xiàn)了量子R轉換器,算子W4～W6實現(xiàn)了量子G轉換器,算子W7～W12實現(xiàn)了量子B轉換器。量子圖像偽彩色編碼量子線路總體設計如圖9所示。

圖9 量子圖像偽彩色編碼量子線路總體設計Fig.9 General design of quantum image pseudo color coding quantum circuit

3 復雜度

3.1 空間復雜度

經(jīng)典偽彩色灰度級-彩色變換法的空間復雜度為(p+q)MS。在基于灰度級-彩色變換法的量子圖像偽彩色編碼中,輸入為量子圖像,占用量子比特;輸出為量子偽彩色圖像,存儲顏色信息需要p量子比特。由圖5可以知道量子R變換器需要1個輔助量子比特;由圖6可以知道量子G變換器需要1個輔助量子比特;由圖4、圖7和圖8可以知道量子B變換器中使用到了6次QSB量子減法器模塊,其中6次QSB減法器模塊需要1個量子比特的初始借位和1個量子比特的公用被減量子位|0〉,此外仍需要24個輔助量子比特用作中間計算。由于QSB模塊受控制位|f4〉控制,因此需要額外的1個輔助量子比特來分解3 CNOT門。量子B變換器總計需要27個輔助量子比特。所以量子圖像偽彩色編碼的空間復雜度為

3.2 時間復雜度

在經(jīng)典偽彩色灰度級-彩色變換法中,圖像的顏色是逐個像素改變的,對于每一個像素,都需要分別判斷灰度值所屬區(qū)間并通過R、G、B轉換器計算相應R、G、B值。因此算法復雜度是3MS。

在量子計算中,量子網(wǎng)絡復雜度取決于所使用CNOT門和1位量子門的數(shù)量。一個t-CNOT門等價于2(t-1)個Toffoli門和1個CNOT門(t＞2),1個Toffoli門等價于6個CNOT門、10個1位量子門[21]。1個t-CNOT門的量子網(wǎng)絡復雜度為32t-31(t＞2),如果t-CNOT的控制位t-1個為“°”,如圖10所示,t-CNOT門的量子網(wǎng)絡復雜度為32t-31+2(t-1)=34t-33(t＞2)。

圖10 t-CNOT的控制位包含“°”Fig.10 The control bits of t-CNOT contains“°”

根據(jù)圖5,W1的量子網(wǎng)絡復雜度為18;W2的量子網(wǎng)絡復雜度為96;W3的量子網(wǎng)絡復雜度為8,所以量子R轉換器的量子網(wǎng)絡復雜度為122。根據(jù)圖6,量子G轉換器模塊W4的量子網(wǎng)絡復雜度為18;W5的量子網(wǎng)絡復雜度為96;W6的量子網(wǎng)絡復雜度為128,所以量子G轉換器的量子網(wǎng)絡復雜度為242。根據(jù)圖4、圖7和圖8,量子B轉換器模塊W7的量子網(wǎng)絡復雜度為144;W8的量子網(wǎng)絡復雜度為173;W9的量子網(wǎng)絡復雜度為536;W10的量子網(wǎng)絡復雜度為161;W11的量子網(wǎng)絡復雜度為69;量子減法器模塊QSB的量子網(wǎng)絡復雜度為250,W12為6位量子減法器,需使用6次受控QSB模塊,量子網(wǎng)絡復雜度為1500,量子B轉換器的量子網(wǎng)絡復雜度為2583。所以所提出的量子圖像偽彩色編碼的量子網(wǎng)絡復雜度為2947。

圖11給出了經(jīng)典灰度級-彩色變換法和基于灰度級-彩色變換法的量子圖像偽彩色編碼分別處理像素為表4所示、色深為256(q=8)的圖像時的算法復雜度比較。很明顯可以看出,隨著像素點的增多,所提處量子算法維持在2947這一常量級別,而經(jīng)典算法時間復雜度按107量級增大。

圖11 經(jīng)典算法和量子算法復雜度比較Fig.11 Complexity comparison between classical algorithm and quantum algorithm

4 經(jīng)典計算機中的仿真實現(xiàn)

圖2所示6個像素點的灰度圖像經(jīng)過所提出量子圖像偽彩色編碼方法處理后,得到的偽彩色圖像如圖12所示。當f(0,0)=224時,RGB=(255,255,0);當f(0,1)=110時,RGB=(184,0,72);當f(0,2)=255時,RGB=(255,255,0);當f(1,0)=0時,RGB=(0,0,255);當f(1,1)=64時,RGB=(0,0,255);當f(1,2)=128時,RGB=(255,0,0),與實驗結果相吻合。驗證了所提處算法的可行性。

圖12 偽彩色處理結果Fig.12 Result of pseudo-color processing

圖13展示了一幅4張CHAOS臟器的灰度圖像經(jīng)過所提出熱金屬碼量子圖像偽彩色編碼處理后的結果,由圖可見處理后圖像增強的效果較好,清晰度較高。

圖13 CHAOS多臟器灰度圖像熱金屬碼偽彩色處理結果Fig.13 Hot metal code pseudo-color processing results of CHAOS multiple organs gray image

5 結論

提出了基于灰度級-彩色變換法的量子圖像偽彩色編碼方法。主要有兩個方面的貢獻:1)首次給出了灰度級-彩色變換法的量子算法版本。相比于密度分層法,灰度級-彩色變換法不需要人為創(chuàng)建顏色映射表,而是根據(jù)函數(shù)一一映射成R、G、B顏色分量。相比于經(jīng)典算法,所提算法實現(xiàn)了指數(shù)級減少內存空間的占用和指數(shù)級降低算法復雜度;2)給出了所提出量子圖像偽彩色編碼方法的量子線路圖。在量子計算機上將實現(xiàn)量子圖像所有像素點的并行運算。