杨 杨， 刘 佳

（黄淮学院，河南 驻马店 463000）

基于量子搜索算法的篮球图像分割研究

杨 杨， 刘 佳

（黄淮学院，河南 驻马店 463000）

为提高篮球图像分割效果，提出了量子搜索算法（QSA）。首先建立篮球分割模型，包括基于3级尺度级的篮球球心、半径建模，基于灰度概率分布的篮球目标分割建模；然后进行量子相位Grover变换，构建加权因子与篮球目标关系，确定最大量子搜素成功概率与量子旋转相位的角度；最后给出了算法流程。实验仿真表明：该算法能有效完成篮球对象的分割，同时分割成功率较高。

计量学；量子搜索算法；篮球图像分割；旋转相位；权系数

1　引 言

在图像分析中，如何利用计算机图像处理、分析篮球比赛并得到感兴趣的各类信息己成为研究的热点［1，2］。目前篮球图像分割的方法有：背景减除算法（Background Subtraction Algorithm，BSA），该方法避免了由混合高斯背景建模带来的高计算性和对变化背景模型低适应的问题［3］，但是存在数据量大的问题；相邻差分算法（Adjacent Difference Algorithm，ADA），通过设定阈值分离运动对象和背景［4］，但阈值往往都是人工设定，存在运动目标和噪声误判的可能；先进先出结构的分水岭算法（Watershed Algorithm，WA），该方法提高了算法的执行速度［5］，但是对图像噪声变化非常敏感，易导致过度分割现象；采用形态运动关联算法（Morphological Motion Correlation Algorithm，MMCA），根据序列图像的运动程度采用多帧处理来获取运动对象［6］，但是不能估计篮球运动信息，鲁棒性差。

本文提出量子搜索算法（Quantum Search Algorithm，QSA），建立尺度级数为3的篮球圆心参数平面确定半径和篮球目标，量子搜索过程中进行相位Grover变换，以最大的概率获得篮球目标元素概率最大值，对于像素搜索问题中的各个像素搜索目标，根据目标的重要程度不同赋予不同的权系数，再将搜索目标表示为一个新的量子叠加态，迭代算子包括黑箱Oracle算子和Hadamard变换相移算子，得到了最大量子搜索成功概率的旋转相位。实验仿真表明该算法能有效完成篮球对象的分割，同时分割成功率较高。

2　篮球分割建模

2.1篮球球心和半径建模

对篮球建立尺度级数为3的圆心参数平面N3（xi，yj），欲分割圆的半径r［a0，a3］，其中3级尺度半径：Sr1∈［a0，a1］，Sr2∈［a1，a3］，Sr3∈［a2，a3］，则圆心的参数平面：

2.2篮球目标分割建模

3　算法模型

对于有n个量子比特的非结构化的数据，N= 2n存在一个量子基态表示量子学中的Dirac符号，称为右矢，C（ωi）=0不满足目标状态，量子搜索算法以最大的几率找到这个目标状态［12］，即通过量子搜索算法找到ωi极大值。

3.1量子搜索算法过程

设HN（N=2n）表示量子态所构成的希尔伯特空间［13，15］，每个布尔函数f（x）：HN→｛0，1｝，将HN划分成两个子空间B1、B2，其中B1由满足条件f（x）= 1的x构成，B2由满足条件f（x）=0的x构成，且B1、B2正交，每一个纯态唯一地表示：

一次任意相位的Grover变换对均匀初态作用后［16］，测得目标元素的概率P、目标元素在搜索空间中所占比例和相位φ=φ之间的变化关系为：

在式中sin2θ∈（0，1/4］，经过一次任意相位的Grover变换后，P在φ=φ得最大值。

3.2搜素成功概率分析

量子搜素算法成功概率较高，对于像素搜索问题中的各个像素搜索目标，根据目标的重要程度不同赋予不同的权系数，再将搜索目标表示为一个新的量子叠加态。

式中：bi为概率幅；ωi为权系数。

迭代算子包括黑箱Oracle算子和Hadamard变换及条件相移算子为：

算法流程：

①输入图像；

②篮球分割建模，确定篮球目标位置；

③量子相位Grover变换，搜索相等的相位和旋转角度；

④更新迭代步数，满足最大搜素成功概率，执行步骤⑤，否则执行步骤③；

⑤输出图像。

4　实验仿真

4.1视觉分割效果

实验仿真采用Matlab平台实现，选取2幅NBA篮球比赛图像如图1、图2所示，分别用BSA、ADA、WA、MMCA、QSA算法对篮球对象分割仿真，结果如图3、图4所示。

图1　№1图像

图2　№2图像

图3　不同算法对№1图像分割结果

图4　不同算法对№2图像分割结果

从分割结果中可以看出QSA算法精确区分了观众席区域和运动员区域，最大限度地剔除了观众席位，保留了感兴趣的区域，有效完成篮球对象的分割，提取的篮球边缘完整、光滑，分割结果受背景的干扰较小，且对边缘模糊和球部分遮挡具有较好的识别。因为本文算法通过探索成功概率取最大值时的旋转相位应满足的条件，来获得成功概率与旋转相位及系统参数之间的函数关系；使旋转相位和系统参数满足这种函数关系，来获得最大的搜索成功概率，QSA算法避免在图像中出现篮球球体遮挡和篮球颜色与背景色相近的现象。BSA算法分割结果出现了对背景变化敏感，不能精确调节与目标相适应，出现误分割现象；ADA算法分割对图像中边缘平滑的部分，分割区域过少；WA算法分割结果出现了分割轮廓偏移，产生过度分割，由于量化误差以及分割区域内细节的影响，产生很多局部最小值，分割中也出现大量细小区域；MMCA算法对初始预测位置的要求较高，如果初始预测不够精确，将无法准确跟踪目标，甚至丢失分割目标，因此分割结果出现了丢失现象。

4.2分割成功率分析

BSA、ADA、WA、MMCA、QSA算法对图像№1、№2、№3分别进行统计分割成功率，然后取分割成功率的平均值，如图5所示为消耗时间与平均分割成功率关系图。

图5　不同算法的消耗时间与平均分割成功率关系

从图5可以看出，在0.4 s内不同算法的平均分割成功率几乎一致，在0.5 s以后QSA算法增长最快，在2.6～3 s之间，各种算法几乎达到平均分割成功率的最大值，QSA算法在所有算法中平均分割成功率最大，这是因为QSA算法根据目标的重要程度不同赋予不同的权系数，为每一个目标量子态赋予一个权系数，对目标量子态进行叠加，依据迭代算子计算迭代次数，在数据中搜索目标重要程度，Grover变换实现了对量子算法的二次加速，不断增加目标量子态的权系数的权值，使各量子基态原先相等的权系数权值发生变化，最终使所求解对应量子基态的权值达到最大，甚至接近于常数1。故在寻优遍历搜索问题中可以大大减少搜索成功所需的迭代次数，旋转相位为φ=0.1π使搜索成功概率达到99%以上。

5　小 结

本文提出了一种基于量子搜索算法的篮球分割方法。实验证明，该算法有效完成篮球对象的分割，分割成功率较高。在进一步的研究中，如何快速地利用所允许的量子变换操作来增加叠加态中解集的权重将是图像分割研究的核心问题。

［1］ 魏宁.篮球运动视频分析系统初步研究［D］.青岛：青岛科技大学，2013.

［2］ 王千.基于视频的篮球持球队员行为预测研究［D］.长沙：中南大学，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］ 郑佳，李江勇.基于背景差分和信息熵的运动目标检测算法［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，Fu 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］ 吴凤和，王金芬，王军，等.基于阈值分割与多边形扫描求交的明暗恢复形状重构模型冗余信息去除［J］.计量学报，2014，35（1）：44-48.

［12］ Soleimanpour-moghadamM，Nezamabadi-pourH，Farsangi 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-），男，河南驻马店人，黄淮学院讲师，硕士，主要从事体育科技方面的研究。hhyangyang@foxmail.com