楊 楊, 劉 佳
(黃淮學(xué)院,河南 駐馬店 463000)
基于量子搜索算法的籃球圖像分割研究
楊 楊, 劉 佳
(黃淮學(xué)院,河南 駐馬店 463000)
為提高籃球圖像分割效果,提出了量子搜索算法(QSA)。首先建立籃球分割模型,包括基于3級(jí)尺度級(jí)的籃球球心、半徑建模,基于灰度概率分布的籃球目標(biāo)分割建模;然后進(jìn)行量子相位Grover變換,構(gòu)建加權(quán)因子與籃球目標(biāo)關(guān)系,確定最大量子搜素成功概率與量子旋轉(zhuǎn)相位的角度;最后給出了算法流程。實(shí)驗(yàn)仿真表明:該算法能有效完成籃球?qū)ο蟮姆指?,同時(shí)分割成功率較高。
計(jì)量學(xué);量子搜索算法;籃球圖像分割;旋轉(zhuǎn)相位;權(quán)系數(shù)
在圖像分析中,如何利用計(jì)算機(jī)圖像處理、分析籃球比賽并得到感興趣的各類信息己成為研究的熱點(diǎn)[1,2]。目前籃球圖像分割的方法有:背景減除算法(Background Subtraction Algorithm,BSA),該方法避免了由混合高斯背景建模帶來(lái)的高計(jì)算性和對(duì)變化背景模型低適應(yīng)的問(wèn)題[3],但是存在數(shù)據(jù)量大的問(wèn)題;相鄰差分算法(Adjacent Difference Algorithm,ADA),通過(guò)設(shè)定閾值分離運(yùn)動(dòng)對(duì)象和背景[4],但閾值往往都是人工設(shè)定,存在運(yùn)動(dòng)目標(biāo)和噪聲誤判的可能;先進(jìn)先出結(jié)構(gòu)的分水嶺算法(Watershed Algorithm,WA),該方法提高了算法的執(zhí)行速度[5],但是對(duì)圖像噪聲變化非常敏感,易導(dǎo)致過(guò)度分割現(xiàn)象;采用形態(tài)運(yùn)動(dòng)關(guān)聯(lián)算法(Morphological Motion Correlation Algorithm,MMCA),根據(jù)序列圖像的運(yùn)動(dòng)程度采用多幀處理來(lái)獲取運(yùn)動(dòng)對(duì)象[6],但是不能估計(jì)籃球運(yùn)動(dòng)信息,魯棒性差。
本文提出量子搜索算法(Quantum Search Algorithm,QSA),建立尺度級(jí)數(shù)為3的籃球圓心參數(shù)平面確定半徑和籃球目標(biāo),量子搜索過(guò)程中進(jìn)行相位Grover變換,以最大的概率獲得籃球目標(biāo)元素概率最大值,對(duì)于像素搜索問(wèn)題中的各個(gè)像素搜索目標(biāo),根據(jù)目標(biāo)的重要程度不同賦予不同的權(quán)系數(shù),再將搜索目標(biāo)表示為一個(gè)新的量子疊加態(tài),迭代算子包括黑箱Oracle算子和Hadamard變換相移算子,得到了最大量子搜索成功概率的旋轉(zhuǎn)相位。實(shí)驗(yàn)仿真表明該算法能有效完成籃球?qū)ο蟮姆指?,同時(shí)分割成功率較高。
2.1籃球球心和半徑建模
對(duì)籃球建立尺度級(jí)數(shù)為3的圓心參數(shù)平面N3(xi,yj),欲分割圓的半徑r[a0,a3],其中3級(jí)尺度半徑:Sr1∈[a0,a1],Sr2∈[a1,a3],Sr3∈[a2,a3],則圓心的參數(shù)平面:
2.2籃球目標(biāo)分割建模
對(duì)于有n個(gè)量子比特的非結(jié)構(gòu)化的數(shù)據(jù),N= 2n存在一個(gè)量子基態(tài)表示量子學(xué)中的Dirac符號(hào),稱為右矢,C(ωi)=0不滿足目標(biāo)狀態(tài),量子搜索算法以最大的幾率找到這個(gè)目標(biāo)狀態(tài)[12],即通過(guò)量子搜索算法找到ωi極大值。
3.1量子搜索算法過(guò)程
設(shè)HN(N=2n)表示量子態(tài)所構(gòu)成的希爾伯特空間[13,15],每個(gè)布爾函數(shù)f(x):HN→{0,1},將HN劃分成兩個(gè)子空間B1、B2,其中B1由滿足條件f(x)= 1的x構(gòu)成,B2由滿足條件f(x)=0的x構(gòu)成,且B1、B2正交,每一個(gè)純態(tài)唯一地表示:
一次任意相位的Grover變換對(duì)均勻初態(tài)作用后[16],測(cè)得目標(biāo)元素的概率P、目標(biāo)元素在搜索空間中所占比例和相位φ=φ之間的變化關(guān)系為:
在式中sin2θ∈(0,1/4],經(jīng)過(guò)一次任意相位的Grover變換后,P在φ=φ得最大值。
3.2搜素成功概率分析
量子搜素算法成功概率較高,對(duì)于像素搜索問(wèn)題中的各個(gè)像素搜索目標(biāo),根據(jù)目標(biāo)的重要程度不同賦予不同的權(quán)系數(shù),再將搜索目標(biāo)表示為一個(gè)新的量子疊加態(tài)。
式中:bi為概率幅;ωi為權(quán)系數(shù)。
迭代算子包括黑箱Oracle算子和Hadamard變換及條件相移算子為:
算法流程:
①輸入圖像;
②籃球分割建模,確定籃球目標(biāo)位置;
③量子相位Grover變換,搜索相等的相位和旋轉(zhuǎn)角度;
④更新迭代步數(shù),滿足最大搜素成功概率,執(zhí)行步驟⑤,否則執(zhí)行步驟③;
⑤輸出圖像。
4.1視覺分割效果
實(shí)驗(yàn)仿真采用Matlab平臺(tái)實(shí)現(xiàn),選取2幅NBA籃球比賽圖像如圖1、圖2所示,分別用BSA、ADA、WA、MMCA、QSA算法對(duì)籃球?qū)ο蠓指罘抡?,結(jié)果如圖3、圖4所示。
圖1 №1圖像
圖2 №2圖像
圖3 不同算法對(duì)№1圖像分割結(jié)果
圖4 不同算法對(duì)№2圖像分割結(jié)果
從分割結(jié)果中可以看出QSA算法精確區(qū)分了觀眾席區(qū)域和運(yùn)動(dòng)員區(qū)域,最大限度地剔除了觀眾席位,保留了感興趣的區(qū)域,有效完成籃球?qū)ο蟮姆指?,提取的籃球邊緣完整、光滑,分割結(jié)果受背景的干擾較小,且對(duì)邊緣模糊和球部分遮擋具有較好的識(shí)別。因?yàn)楸疚乃惴ㄍㄟ^(guò)探索成功概率取最大值時(shí)的旋轉(zhuǎn)相位應(yīng)滿足的條件,來(lái)獲得成功概率與旋轉(zhuǎn)相位及系統(tǒng)參數(shù)之間的函數(shù)關(guān)系;使旋轉(zhuǎn)相位和系統(tǒng)參數(shù)滿足這種函數(shù)關(guān)系,來(lái)獲得最大的搜索成功概率,QSA算法避免在圖像中出現(xiàn)籃球球體遮擋和籃球顏色與背景色相近的現(xiàn)象。BSA算法分割結(jié)果出現(xiàn)了對(duì)背景變化敏感,不能精確調(diào)節(jié)與目標(biāo)相適應(yīng),出現(xiàn)誤分割現(xiàn)象;ADA算法分割對(duì)圖像中邊緣平滑的部分,分割區(qū)域過(guò)少;WA算法分割結(jié)果出現(xiàn)了分割輪廓偏移,產(chǎn)生過(guò)度分割,由于量化誤差以及分割區(qū)域內(nèi)細(xì)節(jié)的影響,產(chǎn)生很多局部最小值,分割中也出現(xiàn)大量細(xì)小區(qū)域;MMCA算法對(duì)初始預(yù)測(cè)位置的要求較高,如果初始預(yù)測(cè)不夠精確,將無(wú)法準(zhǔn)確跟蹤目標(biāo),甚至丟失分割目標(biāo),因此分割結(jié)果出現(xiàn)了丟失現(xiàn)象。
4.2分割成功率分析
BSA、ADA、WA、MMCA、QSA算法對(duì)圖像№1、№2、№3分別進(jìn)行統(tǒng)計(jì)分割成功率,然后取分割成功率的平均值,如圖5所示為消耗時(shí)間與平均分割成功率關(guān)系圖。
圖5 不同算法的消耗時(shí)間與平均分割成功率關(guān)系
從圖5可以看出,在0.4 s內(nèi)不同算法的平均分割成功率幾乎一致,在0.5 s以后QSA算法增長(zhǎng)最快,在2.6~3 s之間,各種算法幾乎達(dá)到平均分割成功率的最大值,QSA算法在所有算法中平均分割成功率最大,這是因?yàn)镼SA算法根據(jù)目標(biāo)的重要程度不同賦予不同的權(quán)系數(shù),為每一個(gè)目標(biāo)量子態(tài)賦予一個(gè)權(quán)系數(shù),對(duì)目標(biāo)量子態(tài)進(jìn)行疊加,依據(jù)迭代算子計(jì)算迭代次數(shù),在數(shù)據(jù)中搜索目標(biāo)重要程度,Grover變換實(shí)現(xiàn)了對(duì)量子算法的二次加速,不斷增加目標(biāo)量子態(tài)的權(quán)系數(shù)的權(quán)值,使各量子基態(tài)原先相等的權(quán)系數(shù)權(quán)值發(fā)生變化,最終使所求解對(duì)應(yīng)量子基態(tài)的權(quán)值達(dá)到最大,甚至接近于常數(shù)1。故在尋優(yōu)遍歷搜索問(wèn)題中可以大大減少搜索成功所需的迭代次數(shù),旋轉(zhuǎn)相位為φ=0.1π使搜索成功概率達(dá)到99%以上。
本文提出了一種基于量子搜索算法的籃球分割方法。實(shí)驗(yàn)證明,該算法有效完成籃球?qū)ο蟮姆指睿指畛晒β瘦^高。在進(jìn)一步的研究中,如何快速地利用所允許的量子變換操作來(lái)增加疊加態(tài)中解集的權(quán)重將是圖像分割研究的核心問(wèn)題。
[1] 魏寧.籃球運(yùn)動(dòng)視頻分析系統(tǒng)初步研究[D].青島:青島科技大學(xué),2013.
[2] 王千.基于視頻的籃球持球隊(duì)員行為預(yù)測(cè)研究[D].長(zhǎng)沙:中南大學(xué),2012.
[3] Zamalieva D,Yilmaz A.Background subtraction for the moving camera:A geometric approach[J].Computer Vision and Image Understanding,2014,127(10):73-85.
[4] 鄭佳,李江勇.基于背景差分和信息熵的運(yùn)動(dòng)目標(biāo)檢測(cè)算法[J].激光與紅外,2014,44(5):563-566.
[5] Malmberg F,Hendriks C L L.An efficient algorithm for exact evaluation of stochastic watersheds[J].Pattern Recognition Letters,2014,47(10):80-84.
[6] Crammond G,Boyd S W,Dulieu-Barton J M.Speckle pattern quality assessment for digital image correlation[J].Optics and Lasers in Engineering,2013,51(12):1368-1378.
[7] Chen H T,Chou C L,F(xiàn)u T S,et al.Recognizing tactic patterns inbroadcastbasketballvideousingplayer trajectory[J].Journal of Visual Communication and Image Representation,2012,23(6):932-947.
[8] Chen H T,Tian M C,Chen Y W,et al.Physics-based balltrackingand3Dtrajectoryreconstructionwith applications to shooting location estimation in basketball video[J].Journal of Visual Communication and Image Representation,2009,20(3):204-216.
[9] Hiroki Okubo,Mont Hubbard.Dentification of basketball parameters forasimulationmodel[J].Procedia Engineering,2010,2(6):3281-3286.
[10] Fan Chen,Christophe De Vleeschouwer.Personalized production of basketball videos from multi-sensored data under limited display resolution[J].Computer Vision and Image Understanding,2010,114(6):667-680.
[11] 吳鳳和,王金芬,王軍,等.基于閾值分割與多邊形掃描求交的明暗恢復(fù)形狀重構(gòu)模型冗余信息去除[J].計(jì)量學(xué)報(bào),2014,35(1):44-48.
[12] Soleimanpour-moghadamM,Nezamabadi-pourH,F(xiàn)arsangi M M.A quantum inspired gravitational search algorithm fornumericalfunctionoptimization[J]. Information Sciences,2014,267(20):83-100.
[13] Tsai J,Hsiao F Y,Li Y J,et al.A quantum search algorithm for future spacecraft attitude determination[J].Acta Astronautica,2011,68(7-8):1208-1218.
[14] Li P C,Li S Y.A Grover quantum searching algorithm based on the weighted targets[J].Journal of Systems Engineering Electronics,2008,19(2):363-369.
[15] Anwar MS,BlazinaD,CarteretHA,etal. Implementing Grover’s quantum search on a parahydrogen based pure state NMR quantum computer[J]. Chemical Physics Letters,2004,400(11):94-97.
[16] Luan L L,Wang Z J,Liu S M.Progress of Grover Quantum Search Algorithm[J].Energy Procedia,2012,16(C):1701-1706.
[17] Liu Y P,Koehler G J.Using modifications to Grover’s Search algorithm for quantum global optimization[J]. European Journal of Operational Research,2010,207(2):620-632.
[18] Joonwoo Bae,Kwon Y,Baek I,et al.Interactionaided continuous time quantum search[J].Chaos,Solitons&Fractals,2005,24(1):103-106.
[19] Sebastian D?rn,Thomas Thierauf.A note on the search for k elements via quantum walk[J].Information Processing Letters,2010,110(22):975-978.
Basketball Image Segmentation Research Based on Quantum Search Algorithm
YANG Yang, LIU Jia
(Huanghuai University,Zhumadian,Henan 463000,China)
In order to improve the effect of basketball image segmentation,quantum search algorithm(QSA)is proposed.Firstly,basketball segmentation model was established,including basketball center and radius based on three scales,and basketball target was segmented based on gray probability distribution.Secondly,quantum phase was transformed based on quantum phase Grover conversion in order to establish weighting factor and basketball target relation,and maximum quantum search success possibility and angle of quantum rotation phase was determined.Finally,quantum search algorithm process was given.Simulation indicated that quantum search algorithm can accomplish basketball object segmentation effectively,and segmentation success rate is higher.
metrology;quantum search algorithm;basketball image segmentation;rotation phase;weight coefficient
TB96
A
1000-1158(2015)05-0464-05
10.3969/j.issn.1000-1158.2015.05.04
2014-11-14;
2015-03-05
河南省科技廳重點(diǎn)研究項(xiàng)目(9412011Y1330)
楊楊(1986-),男,河南駐馬店人,黃淮學(xué)院講師,碩士,主要從事體育科技方面的研究。hhyangyang@foxmail.com