基于量子指針的量子灰度圖像處理

艾金根，周日貴

（1.江西省科技項目服務(wù)中心，江西南昌，3300462.華東交通大學(xué)信息工程學(xué)院，江西南昌，330013）

量子力學(xué)與計算機的結(jié)合起源于Benioff利用量子力學(xué)來描述計算機［1］。1982年，F(xiàn)eynman所提出的量子計算機［2］使得量子力學(xué)這門深度、廣度兼具的學(xué)科與計算機完全融合，于是也就有了量子計算發(fā)展的根本性突破。類似于經(jīng)典計算機，要使量子計算機的體系更加完善，必然要有適應(yīng)于該體系特點的獨立算法來完成各種復(fù)雜的運算操作。有效利用量子并行性和量子態(tài)的疊加、糾纏、坍縮等性質(zhì)，Deutsch提出了Deutsch量子算法［3］，該算法既證明了量子并行的特性，也體現(xiàn)出了相比于經(jīng)典計算機而言，量子計算機的高速性和高效性。1994年，Shor提出了量子質(zhì)因子分解算法［4］。大數(shù)因子分解問題屬于一類典型的NP（non-deterministic polynomial）完全問題，而Shor算法所解決的這類問題正是經(jīng)典算法無法解決的。Grover量子搜索算法［5］出現(xiàn)于1995年，該算法所做出的最大貢獻在于將搜索復(fù)雜度從經(jīng)典計算中的N縮小到了

N。而對Grover算法的改進亦是接踵而至［6-8］。量子算法的出現(xiàn)解決了很多經(jīng)典計算所無法解決的問題，正因為這些優(yōu)勢而出現(xiàn)了更多與量子相結(jié)合的綜合研究領(lǐng)域［9］，量子圖像處理便是其中之一。

量子圖像處理發(fā)展至今，其發(fā)展方向大致可分為三類：第一類是將圖像信息存儲于量子狀態(tài)的量子態(tài)存儲表達式；第二類是將經(jīng)典數(shù)字圖像中的各種變換向量子領(lǐng)域擴展；第三類則是將主要精力放在量子圖像幾何變換中。Qubit Lattice［10-11］、Real Ket［12］和 Flexible Representation ofQuantum Image（FRQI）［13］表達式的提出歸屬于第一類。Qubit Lattice和Real Ket都是基于量子糾纏系統(tǒng)提出的，不同的是，前者的目的在于圖像處理的各個環(huán)節(jié)，而后者則主要作用于圖像壓縮。FRQI的提出具有普遍意義，在圖像存儲、壓縮及幾何變換中都能夠有很好的發(fā)揮［14-16］。本文作者所提出的基于灰度圖像的量子圖像表達式，亦屬于第一類。經(jīng)典數(shù)字圖像變換向量子方向延伸的主要有量子小波變換［17］，量子傅里葉變換［9］和量子離散余弦變換［18-19］。這些變換都充分利用了量子的并行、疊加、糾纏等特性，使得各種變換量子形式比經(jīng)典形式在作用和效率等方面都有很明顯的完善［9］。在參考文獻［15-16］中，作者給出了多類量子幾何變換的酉變換算子，并通過這些變換設(shè)計出量子線路［20-21］，從理論上證明了幾何變換的應(yīng)用性和可實施性。

在本文中，作者提出了一種表示較為簡便的灰度圖像量子表達式。在經(jīng)典彩色圖像中，像素擁有顏色與位置兩個屬性。而在灰度圖像中，每個像素都是以其灰度值和位置兩個方面來表示的，灰度值的范圍較小，這就簡化了表達式的表示形式。所以將表達式向彩色圖像延伸是今后可以繼續(xù)研究的一個方向。另外，在所提出表達式的基礎(chǔ)上，作者提出了一個新的概念——量子指針。這里所提出的量子指針同經(jīng)典計算機中的指針有相似的地方，但也有很大的不同，其目的是要讓量子圖像的存儲表示更加便捷，使圖像在變換的過程中有更高的效率和更好的效果。

1 灰度圖像量子表達式

1.1 表述

在經(jīng)典灰度圖像中，圖像沒有顏色信息，色彩飽和度為零，每一個像素都是由其灰度信息和位置信息構(gòu)成的，而灰度則分為256個級別，從0到255。同樣，在量子灰度圖像中，圖像的像素由灰度和位置來表示，表達式如下：

在經(jīng)典數(shù)字圖像表示中，每一個像素都可以由坐標表示，那么根據(jù)橫縱坐標的表示形式以及像素的表達方式可以將量子灰度圖像的位置狀態(tài)表示進一步進行拆分，即

需注意的是，表達式中的M0，M1，M2，M3所代表的都是二進制字符串，因為圖中每一個像素的灰度都不同，所以M0，M1，M2，M3互不相等，并且每一個位置都有唯一的灰度值。

1.2 證明

由量子算法可知，要證明該表達式的成立就是要從所制備的量子初始態(tài)，通過量子門變換向表達式的存儲狀態(tài)進行轉(zhuǎn)換。

圖1 2×2灰度圖像Fig.1 2×2 gray image

第二步：應(yīng)用Hadamard變換H?2n，即將2n個H門同時作用于量子初始態(tài)的2n個量子比特上。經(jīng)過Hadamard門的作用后，可得中間量子態(tài)：

2 量子指針

在經(jīng)典計算機中，指針是用來表示內(nèi)存單元存儲的地址，通過指針就能找到以它為地址的內(nèi)存單元，也就是說一個變量的地址就是該變量的指針。在灰度圖像量子表達式中，灰度表示使用的是8位的二進制字符串，位置表示使用的亦是二進制字符串，用圖表示也就是每一個像素無論是位置還是灰度信息其表達形式都是二進制的字符串。對于量子灰度圖像而言，每一個像素都由灰度值和其位置表示而成，這二者的組合恰好類似于經(jīng)典計算機中的指針，于是產(chǎn)生了量子指針的想法。

2.1 雙向性

量子指針并不同于經(jīng)典指針。在經(jīng)典指針中，地址就是指針，并且這種表示是固定的。但在量子指針中，指針并不是固定的，而是具有雙向指向性的。也就是說，在灰度值與位置值二者中，灰度值可以表示為指針，位置值也可以表示為指針，而這種選擇則是根據(jù)我們所需要進行的量子圖像處理具體操作來決定的。量子指針的雙向性具體表述為

a.當量子灰度圖像的灰度值表示量子指針時，圖像的位置值即為指針所指向的內(nèi)容；

b.當量子灰度圖像的位置值表示量子指針時，圖像的灰度值即為指針所指向的內(nèi)容。

需注意，在一幅正常的灰度圖像中，各像素的灰度值不可避免的會有相同的情況，所以在以灰度值作為量子指針時就會有相同的指針。而同時，這種表示方式方便了像素量子狀態(tài)的存儲，在無形中便將各像素的量子狀態(tài)進行了分類，使得在進行某些處理過程時，操作變得相對簡單。

灰度值與位置值二者指針選擇的依據(jù)就是要看在不同的圖像處理過程中，選用哪一個作為指針時，能使處理過程相對簡單，較易施行。例如當我們需要調(diào)整圖像中同一灰度像素的灰度值時，我們就可以將灰度看作指針，找到該灰度的指針，然后直接改變灰度值，這樣指針對應(yīng)位置的灰度也就隨之改變了。看到這個例子必然會想到，如果將位置看作量子指針會產(chǎn)生哪些便捷作用？這里就涉及到了量子指針的下一個性質(zhì)——子塊性。

2.2 子塊性

量子指針的子塊性是指將指針進行塊的劃分與組合。因為指針的表達式是二進制的字符串，由0和1組成，所以按照0，1的分隔可以對量子指針進行不同類型的劃分。在以位置值作為量子指針時，當遇到像素較多的情況時，我們可以將指針進行分塊（或者拆分）表示。同理，當灰度值作為量子指針時，我們同樣可以將表示灰度的二進制字符串劃分，將不同灰度的位置劃分到一個大的子塊中。

3 量子灰度圖像存儲應(yīng)用

由于量子指針的雙向性，量子指針有灰度和位置兩種可能性，所以量子灰度圖像的存儲依然按照量子指針的分類進行劃分。當以像素灰度作為量子指針時，指針所指向的單元則為像素的位置信息；當以像素的位置作為量子指針時，指針指向的是像素的灰度。

3.1 圖像的存儲

3.1.1 基于量子灰度指針的存儲

在所提出的表達式中，|M〉 用于編碼圖像的灰度信息，假定將灰度信息作為量子指針。在一幅固定的灰度圖像中，每一個像素都有灰度信息，并且這些像素中都會有一些像素的灰度是相同的。將同一灰度值的灰度指針指向具有相同灰度信息的像素位置，這樣所建立起來的關(guān)系便不再是經(jīng)典圖像中一對一的關(guān)系，而是一對多的關(guān)系，一對多的關(guān)系使得像素不用單一變化，而是能在形成像素子塊之后，進行較大規(guī)模地變換。因為灰度值是在0到255之間變化的，那么將同一灰度值的位置進行統(tǒng)一存儲，最多也只是需要256個單位的量子態(tài)進行存儲。

3.1.2 基于量子位置指針的存儲

基于量子位置指針的存儲主要依靠的是量子指針的子塊性，通過對位置信息比特的子塊劃分，達到分塊存儲圖像像素信息的目的。

3.1.3 混合指針

從兩種量子指針的描述中，我們不難發(fā)現(xiàn)，二者存在結(jié)合的可能性。在量子灰度指針中，對于同一灰度而言，其指向的所有位置仍然能夠進行子塊的劃分，從而產(chǎn)生量子位置子指針。相同的道理，在被處理的像素塊中，如果塊中所包含的灰度種類并不是特別多，還是可以以灰度為依據(jù)進行結(jié)合。這個也可以作為以后研究實際應(yīng)用中的一個方向。

從以上的兩種量子指針的對存儲的表示來看，對于不同的量子圖像處理操作，兩者各有優(yōu)勢，所以在各種不同的操作中選擇最恰當?shù)闹羔樖橇孔又羔槕?yīng)用的關(guān)鍵。

3.2 灰度變換

灰度變換所要達到的目的是改變圖像中的某一灰度值，并且要求灰度為該灰度值的所有像素都必須改變，也就是說該灰度所對應(yīng)所有位置的灰度值都要相應(yīng)發(fā)生改變。

首先完成如3.1節(jié)所描述的基于灰度指針的量子圖像存儲，然后對圖像的灰度量子比特進行處理。因為灰度值的范圍是0～255，所以需要的是一個最多8位的二進制字符串的表示。因此灰度值的變化就是這8位字符0與1的變化。將原始灰度值同目標灰度值進行對比，找出兩者不同的比特位，然后通過swap門，實現(xiàn)0與1的變換。

3.3 位置變換

位置變換是基于量子位置指針的變換，屬于量子圖像幾何變換，是實現(xiàn)與位置移動及改變相關(guān)的變換。下面將用一幅8×8的灰度圖像來說明位置的變換。

圖3所描述的就是上面操作的存儲與變換過程。首先將位置|P1〉進行存儲。橫向來看圖3所示的交換圖示，虛線框a便是量子指針的第一個子塊，也就是指針的第1層；第2個子塊是一個選擇塊，提供選擇的量子比特是0和1；第3個子塊是由“11”組成的子塊；第4個子塊同樣是一個選擇塊，由0，1構(gòu)成。從我們所劃分的子塊來看，需要做出變換的是第一個子塊，即虛線框a中箭頭所示的1到0的轉(zhuǎn)換，而第2，3，4子塊則構(gòu)成了一個存儲的完全配對組合，如圖中的虛線框b所示。將量子比特字符串分塊存儲，能讓我們很快找到需要變換的塊，從而之間實施比特位的轉(zhuǎn)換，而不同圖像的不同子塊劃分也能改變圖像處理的效率。變換完成后的圖像如圖4所示。

圖2 8×8原始灰度圖像Fig.2 8×8 originalgrey image

如圖5所示的是一組移動組圖，目的是要通過有內(nèi)容圖像塊同空白塊的不斷交換達到塊的移動，從而將圖像從Ⅰ所示的原始圖像得到Ⅵ所示的我們所需要的圖像。每幅圖像都是16×16的灰度圖像，同時將整幅圖像劃分為16個大小尺寸等同的塊，然后通過移動這些塊來完成整幅圖像。首先描述塊移動的第一步，也就是將塊2同空白塊16的交換為例。

像素塊2和16都是由4×4個像素組成。依據(jù)表達式（2），每個像素的位置表示都是由8位的量子比特組成。塊16和塊2的位置集合為（量子比特字符串過長，未在圖中標出，參考可見圖2）

圖3 量子位交換圖Fig.3 Quantum bit swap

圖4 8×8目標灰度圖像Fig.4 8×8 targetgrey image

圖5 原始圖像、目標圖像及圖像變換過程中所得到的中間圖像Fig.5 Original image，target imageandm idd le imagegotby the image transformation

完成了圖5中Ⅰ到Ⅱ的轉(zhuǎn)換，那么其他的轉(zhuǎn)換便是類似的。從原始圖像Ⅰ到目標圖像Ⅵ共需要進行5次轉(zhuǎn)換，圖6所完成的是第一步變換，其他的4次存儲轉(zhuǎn)換的交換同理。

相比于其他的量子圖像幾何變換，使用量子指針首先在形式上使得像素的移動與變換不再是每一個像素的單獨變化，而是以大小不一的像素塊為單位進行變化，這樣能減少不必要的操作冗余，簡化操作步驟。再者，量子指針的指向作用能產(chǎn)生一系列的連鎖反應(yīng)，縮短鎖定操作范圍的時間，提升圖像處理操作的效率。

4 總結(jié)與展望

圖6 變換第一步：塊16同塊2的交換Fig.6 First transformation：exchangebetween 16 and 2

根據(jù)灰度圖像像素的灰度屬性和位置屬性提出了一種量子灰度圖像的表達式，并依據(jù)這種圖像的表達形式提出了量子指針的新概念，在基于量子指針性質(zhì)的基礎(chǔ)上進行了量子灰度圖像理論上的灰度變換和位置變換。在不同的圖像處理操作中使用不同的量子指針類型，能簡化操作的復(fù)雜性。從示例可以看出，量子指針的連接作用使得圖像在改變灰度或者位置信息的基礎(chǔ)上便能完成整個圖像變換的操作，復(fù)雜度減半。

［1］ PAUL BENIOFF.Quantum mechanical ham iltonian models of turing machines［J］.Journal of Statistical Physics，1982，29（3）：515-546.

［2］ RICHARD PFEYNMAN.Simulating physicsw ith computers［J］.International Journal of Theoretical Physics，1982，21（6/7）：467-488.

［3］ DAVID DEUTSCH.Quantum theory，the church-turing principle and the universal quantum computer［J］.Proceeding of the Royal Society of London，1985，400（18）：97-117.

［4］ PETERW SHOR.Algorithms for quantum computation：descrete log and factoring［C］//Foundations of Computer Science，Preceedingsof the 35thAnnualSymposium，Washington：Proceedingsof IEEE，1994：124-134.

［5］ LOV K GROVER.A fast quantum mechanical algorithm for database search［C］//Proceedings of the twenty-eight annual ACM symposium on Theory of computing，New York：ACM，1996：212-219.

［6］GUILU LONG，WEILIN ZHANG，YAN SONG LI，etal.Arbitrary phase rotation of themarked state can not be used for grover’squantum search algorithm［J］.Commun Theor Phys，1999，32：335-338.

［7］GUILU LONG.Groveralgorithm w ith zero theoretical failure rate［J］.PhysicalReview A，2001，64（2）：22307-0.

［8］ GUILU LONG，XIAO LI，YANG SUN.Phasematching condition for quantum search w ith a generalized initial state［J］.Physics LettersA，2002，294：143-152.

［9］NIELSEN M，CHUANG IL，Quantum computation and quantum information［M］.Cambridge：Cambridge University Press，2000：216-271.

［10］VENEGASANDRACA SE，BOSE S.Storing，processing and retrieving and image using quantum mechanics［J］.Quantum Information and Computation，2003，5105：137-147.

［11］ VENEGAS-ANDRACA SE，BALL JL.Processing images in entangled quantum systems［J］.Quantum Information Processing，2010，9（1）：1-11.

［12］JOS′E I.LATORRE.Image compression and entanglement［J］.Arxiv：Quant-ph10510031V1，2005：1-4.

［13］PHUC Q LE，F(xiàn)ANGYAN DONG，KAORU HIROTA.A flexible representation of quantum images for polynomial preparation，image compression，and processing operations［J］.Quantum Information Processing，2011，10（1）：63-84.

［14］PHUC Q LE，ABDULLAH M ILIYASU，F(xiàn)ANGYAN DONG，etal.Efficient color transformations on quantum images［J］.JournalofAdvanced Computational Intelligence and Intelligent Informatics，2011，15（6）：698-706.

［15］PHUC Q LE，ABDULLAH M ILIYASU，F(xiàn)ANGYAN DONG，etal.Fastgeometric transformations on quantum images［J］.IAENG International JournalofApplied Mathematics，2010，40（3）：2-12.

［16］ PHUC Q LE，ABDULLAH M ILIYASU，F(xiàn)ANGYAN DONG，et al.Strategies for designing geometric transformations on quantum images［J］.TheoreticalComputer Science，2010，412（15）：1406-1418.

［17］ AM IR FIJANY，COLIN PW ILLIAMS.Quantum wavelet transforms：fast algorithms and complete circuits［J］.Quantum Computing and Quantum Communications，1999，1509：10-33.

［18］ANDREASKLAPPENECKER，MARTIN ROTTELER.Discrete cosine transforms on quantum computers［C］//Image and Signal Processing and Analysis，New York：IEEEPress，2001：464-468.

［19］PANG CHAOYANG，ZHOU ZHENGWEI，GUO GUANGCAN.Quantum discrete cosine transform for image compression［J］.Quantum Physics（quant-ph），2006，quant-ph/0601043v2.

［20］ ADRIANO BARENCO，CHARLES H.Elementary gates for quantum computation［J］.Physical Review A，1995（52）：3457-3467.

［21］ GLENN BEACH，CHRIS LOMONT，CHARLESCOHEN.Quantum Image Processing（QuIP）［C］//32ndApplied Imagery Pattern RecognitionWorkshop，New York：IEEEPress，2003：39-44.

［22］周日貴，張滿群，吳茜，施洋.新型BCD加法器及其可逆邏輯實現(xiàn)［J］.華東交通大學(xué)學(xué)報，2011，28（4）：1-6.