楊 楊， 劉 佳

（黃淮學(xué)院，河南 駐馬店 463000）

基于量子搜索算法的籃球圖像分割研究

楊 楊， 劉 佳

（黃淮學(xué)院，河南 駐馬店 463000）

為提高籃球圖像分割效果，提出了量子搜索算法（QSA）。首先建立籃球分割模型，包括基于3級尺度級的籃球球心、半徑建模，基于灰度概率分布的籃球目標(biāo)分割建模；然后進(jìn)行量子相位Grover變換，構(gòu)建加權(quán)因子與籃球目標(biāo)關(guān)系，確定最大量子搜素成功概率與量子旋轉(zhuǎn)相位的角度；最后給出了算法流程。實驗仿真表明：該算法能有效完成籃球?qū)ο蟮姆指?，同時分割成功率較高。

計量學(xué)；量子搜索算法；籃球圖像分割；旋轉(zhuǎn)相位；權(quán)系數(shù)

1　引 言

在圖像分析中，如何利用計算機圖像處理、分析籃球比賽并得到感興趣的各類信息己成為研究的熱點［1，2］。目前籃球圖像分割的方法有：背景減除算法（Background Subtraction Algorithm，BSA），該方法避免了由混合高斯背景建模帶來的高計算性和對變化背景模型低適應(yīng)的問題［3］，但是存在數(shù)據(jù)量大的問題；相鄰差分算法（Adjacent Difference Algorithm，ADA），通過設(shè)定閾值分離運動對象和背景［4］，但閾值往往都是人工設(shè)定，存在運動目標(biāo)和噪聲誤判的可能；先進(jìn)先出結(jié)構(gòu)的分水嶺算法（Watershed Algorithm，WA），該方法提高了算法的執(zhí)行速度［5］，但是對圖像噪聲變化非常敏感，易導(dǎo)致過度分割現(xiàn)象；采用形態(tài)運動關(guān)聯(lián)算法（Morphological Motion Correlation Algorithm，MMCA），根據(jù)序列圖像的運動程度采用多幀處理來獲取運動對象［6］，但是不能估計籃球運動信息，魯棒性差。

本文提出量子搜索算法（Quantum Search Algorithm，QSA），建立尺度級數(shù)為3的籃球圓心參數(shù)平面確定半徑和籃球目標(biāo)，量子搜索過程中進(jìn)行相位Grover變換，以最大的概率獲得籃球目標(biāo)元素概率最大值，對于像素搜索問題中的各個像素搜索目標(biāo)，根據(jù)目標(biāo)的重要程度不同賦予不同的權(quán)系數(shù)，再將搜索目標(biāo)表示為一個新的量子疊加態(tài)，迭代算子包括黑箱Oracle算子和Hadamard變換相移算子，得到了最大量子搜索成功概率的旋轉(zhuǎn)相位。實驗仿真表明該算法能有效完成籃球?qū)ο蟮姆指?，同時分割成功率較高。

2　籃球分割建模

2.1籃球球心和半徑建模

對籃球建立尺度級數(shù)為3的圓心參數(shù)平面N3（xi，yj），欲分割圓的半徑r［a0，a3］，其中3級尺度半徑：Sr1∈［a0，a1］，Sr2∈［a1，a3］，Sr3∈［a2，a3］，則圓心的參數(shù)平面：

2.2籃球目標(biāo)分割建模

3　算法模型

對于有n個量子比特的非結(jié)構(gòu)化的數(shù)據(jù)，N= 2n存在一個量子基態(tài)表示量子學(xué)中的Dirac符號，稱為右矢，C（ωi）=0不滿足目標(biāo)狀態(tài)，量子搜索算法以最大的幾率找到這個目標(biāo)狀態(tài)［12］，即通過量子搜索算法找到ωi極大值。

3.1量子搜索算法過程

設(shè)HN（N=2n）表示量子態(tài)所構(gòu)成的希爾伯特空間［13，15］，每個布爾函數(shù)f（x）：HN→｛0，1｝，將HN劃分成兩個子空間B1、B2，其中B1由滿足條件f（x）= 1的x構(gòu)成，B2由滿足條件f（x）=0的x構(gòu)成，且B1、B2正交，每一個純態(tài)唯一地表示：

一次任意相位的Grover變換對均勻初態(tài)作用后［16］，測得目標(biāo)元素的概率P、目標(biāo)元素在搜索空間中所占比例和相位φ=φ之間的變化關(guān)系為：

在式中sin2θ∈（0，1/4］，經(jīng)過一次任意相位的Grover變換后，P在φ=φ得最大值。

3.2搜素成功概率分析

量子搜素算法成功概率較高，對于像素搜索問題中的各個像素搜索目標(biāo)，根據(jù)目標(biāo)的重要程度不同賦予不同的權(quán)系數(shù)，再將搜索目標(biāo)表示為一個新的量子疊加態(tài)。

式中：bi為概率幅；ωi為權(quán)系數(shù)。

迭代算子包括黑箱Oracle算子和Hadamard變換及條件相移算子為：

算法流程：

①輸入圖像；

②籃球分割建模，確定籃球目標(biāo)位置；

③量子相位Grover變換，搜索相等的相位和旋轉(zhuǎn)角度；

④更新迭代步數(shù)，滿足最大搜素成功概率，執(zhí)行步驟⑤，否則執(zhí)行步驟③；

⑤輸出圖像。

4　實驗仿真

4.1視覺分割效果

實驗仿真采用Matlab平臺實現(xiàn)，選取2幅NBA籃球比賽圖像如圖1、圖2所示，分別用BSA、ADA、WA、MMCA、QSA算法對籃球?qū)ο蠓指罘抡妫Y(jié)果如圖3、圖4所示。

圖1　№1圖像

圖2　№2圖像

圖3　不同算法對№1圖像分割結(jié)果

圖4　不同算法對№2圖像分割結(jié)果

從分割結(jié)果中可以看出QSA算法精確區(qū)分了觀眾席區(qū)域和運動員區(qū)域，最大限度地剔除了觀眾席位，保留了感興趣的區(qū)域，有效完成籃球?qū)ο蟮姆指?，提取的籃球邊緣完整、光滑，分割結(jié)果受背景的干擾較小，且對邊緣模糊和球部分遮擋具有較好的識別。因為本文算法通過探索成功概率取最大值時的旋轉(zhuǎn)相位應(yīng)滿足的條件，來獲得成功概率與旋轉(zhuǎn)相位及系統(tǒng)參數(shù)之間的函數(shù)關(guān)系；使旋轉(zhuǎn)相位和系統(tǒng)參數(shù)滿足這種函數(shù)關(guān)系，來獲得最大的搜索成功概率，QSA算法避免在圖像中出現(xiàn)籃球球體遮擋和籃球顏色與背景色相近的現(xiàn)象。BSA算法分割結(jié)果出現(xiàn)了對背景變化敏感，不能精確調(diào)節(jié)與目標(biāo)相適應(yīng)，出現(xiàn)誤分割現(xiàn)象；ADA算法分割對圖像中邊緣平滑的部分，分割區(qū)域過少；WA算法分割結(jié)果出現(xiàn)了分割輪廓偏移，產(chǎn)生過度分割，由于量化誤差以及分割區(qū)域內(nèi)細(xì)節(jié)的影響，產(chǎn)生很多局部最小值，分割中也出現(xiàn)大量細(xì)小區(qū)域；MMCA算法對初始預(yù)測位置的要求較高，如果初始預(yù)測不夠精確，將無法準(zhǔn)確跟蹤目標(biāo)，甚至丟失分割目標(biāo)，因此分割結(jié)果出現(xiàn)了丟失現(xiàn)象。

4.2分割成功率分析

BSA、ADA、WA、MMCA、QSA算法對圖像№1、№2、№3分別進(jìn)行統(tǒng)計分割成功率，然后取分割成功率的平均值，如圖5所示為消耗時間與平均分割成功率關(guān)系圖。

圖5　不同算法的消耗時間與平均分割成功率關(guān)系

從圖5可以看出，在0.4 s內(nèi)不同算法的平均分割成功率幾乎一致，在0.5 s以后QSA算法增長最快，在2.6～3 s之間，各種算法幾乎達(dá)到平均分割成功率的最大值，QSA算法在所有算法中平均分割成功率最大，這是因為QSA算法根據(jù)目標(biāo)的重要程度不同賦予不同的權(quán)系數(shù)，為每一個目標(biāo)量子態(tài)賦予一個權(quán)系數(shù)，對目標(biāo)量子態(tài)進(jìn)行疊加，依據(jù)迭代算子計算迭代次數(shù)，在數(shù)據(jù)中搜索目標(biāo)重要程度，Grover變換實現(xiàn)了對量子算法的二次加速，不斷增加目標(biāo)量子態(tài)的權(quán)系數(shù)的權(quán)值，使各量子基態(tài)原先相等的權(quán)系數(shù)權(quán)值發(fā)生變化，最終使所求解對應(yīng)量子基態(tài)的權(quán)值達(dá)到最大，甚至接近于常數(shù)1。故在尋優(yōu)遍歷搜索問題中可以大大減少搜索成功所需的迭代次數(shù)，旋轉(zhuǎn)相位為φ=0.1π使搜索成功概率達(dá)到99%以上。

5　小 結(jié)

本文提出了一種基于量子搜索算法的籃球分割方法。實驗證明，該算法有效完成籃球?qū)ο蟮姆指?，分割成功率較高。在進(jìn)一步的研究中，如何快速地利用所允許的量子變換操作來增加疊加態(tài)中解集的權(quán)重將是圖像分割研究的核心問題。

［1］ 魏寧.籃球運動視頻分析系統(tǒng)初步研究［D］.青島：青島科技大學(xué)，2013.

［2］ 王千.基于視頻的籃球持球隊員行為預(yù)測研究［D］.長沙：中南大學(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］ 鄭佳，李江勇.基于背景差分和信息熵的運動目標(biāo)檢測算法［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］.計量學(xué)報，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

河南省科技廳重點研究項目（9412011Y1330）

楊楊（1986-），男，河南駐馬店人，黃淮學(xué)院講師，碩士，主要從事體育科技方面的研究。hhyangyang@foxmail.com