一種基于CamShift算法和隨機Hough變換的球形目標跟蹤算法

張晨+王紅茹+丁文+王云輝+錢康

摘 要 為提高視覺移動機器人對球形目標的跟蹤精度與實時性，文章利用CamShift算法具有依靠顏色模型能夠對目標快速跟蹤的特點，并結合隨機Hough圓變換提出一種實效球形目標跟蹤算法。實驗結果表明，提出的方法能夠實現簡單室內環境下球形目標的快速準確跟蹤。

關鍵詞 目標跟蹤；球形目標；CamShift算法；隨機Hough變換

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1671-7597（2014）04-0054-02

計算機視覺應用中，目標跟蹤一直是研究的熱點內容之一。而在目標跟蹤研究中，最值得關心的就是跟蹤算法的實時性和準確性。為此，相關學者提出了很多不同的方法，其中應用最為廣泛的是Gary R Bradski提出的基于自適應均值漂移（Continuously adaptive mean shift，CamShift）算法。CamShift算法依靠視頻圖像的色彩信息來實現對目標的跟蹤，其運算速度快且比較適合不太復雜的背景下的目標跟蹤，因此適合室內移動機器人對目標的跟蹤。

而對于基于視覺的室內移動機器人目標跟蹤，僅僅依靠CamShift這種依靠顏色模型的跟蹤方法，無法在照度不均的情況下獲得圓形目標物的精確位置信息。而隨機Hough圓變換具有對圓形目標識別精度高且速度快的特點。為此，本文提出采用CamShift算法與隨機Hough變換結合的方法以實現對球形目標的快速、準確跟蹤。

1 算法原理

1.1 CamShift算法介紹

CamShift算法實際上是連續自適應的MeanShift算法的簡稱。該算法降低了由光照亮度變化對跟蹤效果的影響，并且利用基于像素顏色概率分布信息進行目標跟蹤的方法，使算法的效率比較高。CamShift算法采用基于概率密度的梯度攀升來尋找局部最優的思想對每一幀圖像運用MeanShift算法做處理。根據前一幀圖像的搜索結果自適應調整搜索窗的大小，從而實現對當前圖像中目標的定位。

算法主要步驟如下。

1）首先將當前幀圖像由RGB空間轉換到HSV空間，并將當前圖像整幅都作為搜索范圍。

2）設定搜索窗口（SearchWindow）大小與位置的初始值并計算窗口內的色度（Hue）分量概率分布直方圖。

3）對當前圖像的每一個像素采用其顏色的概率值進行替換，從而得到顏色概率分布圖。

4）在顏色概率分布圖中選取搜索窗。

5）計算零階矩：

計算一階矩：

計算搜索窗的質心：

6）調整搜索窗大小，窗口寬度為；長度為1.2w。

7）將SearchWindow的中心移動到質心位置，當移動距離超過了設定的閾值時，則跳轉到步驟5），當SearchWindow的中心與質心間的距離小于一個預設值或者迭代次數達到最大時，停止計算。

8）在下一幀輸入的圖像中用上一步中的結果再一次計算搜索窗口的參數，然后跳轉到步驟2）繼續目標搜索。

1.2 隨機Hough圓變換介紹

Hough變換是一種在圖像中尋找直線、圓以及其他簡單形狀的方法。其基本思想是將原始圖像中的曲線或者直線檢測問題轉變成在參數空間中聚類求峰值問題。由于圓形包含3個自由參數，需要在三維空間中投票求峰值，其計算量很大且對內存消耗大，算法運算時間長。因此XU等人提出了隨機Hough變換（Randomized Hough Transform，RHT），使用了3個新的操作機制，即在圖像空間中的隨機抽樣、參數空間中的動態鏈接列表以及連接圖像空間和參數空間的收斂映射，從而加快了運算速度和提高了內存的利用率。然而隨機采樣會引入大量的無效累積和無效采樣，在處理復雜背景和較大圖像時對算法識別性能有較大的影響。因此有學者提出了改進的RHT算法，但不可否認的是在處理背景簡單尤其是小圖像的識別時，隨機Hough變換運算速度很快，識別精度高。

1.3 基于CamShift與RHT的球體跟蹤方法

由于CamShift算法是運用物體顏色信息和聚類的方式跟蹤視頻序列中的運動目標，因此算法具有較高的執行效率。而在雙目移動機器人運用視差法計算球體目標三維坐標時，需要輸入球體在圖像中的二維坐標位置，二維坐標位置的誤差過大會影響目標的定位及機器人姿態的調整。但是僅僅依靠CamShift算法返回的搜索區域的質心無法較精確的識別圓形目標的圓心及半徑，考慮針對小圖像運用隨機Hough圓變換的具有高識別精度和運算速度快的特點，因此將CamShift和RHT兩種算法結合并運用在簡單的室內環境下對球形目標的跟蹤上。在前文闡述的CamShift算法步驟中，步驟5）、6）、7）其實就是MeanShift算法的主要步驟，則CamShift與RHT結合的球體跟蹤識別方法主要步驟表述如下。

1）確定初始目標的位置及區域并計算目標的H分量直方圖。

2）利用直方圖計算反向投影圖。

3）采用MeanShift算法在上一步的反向投影圖中進行迭代搜索，當計算結果收斂或達到最大迭代次數時停止計算。

4）利用MeanShift算法返回的搜索窗口的中心位置，取輸入幀圖像在周圍的局部圖像保存為子圖像（SubImage），子圖像的高度（subheight）和寬度度（subwidth）與搜索窗的寬度和長度相等。

采用隨機Hough圓變換對SubImage進行圓形特征檢測。

在子圖像中若識別出圓形特征則返回其在原始圖像當中的位置，假設子圖像中圓心坐標為，原始圖像中的圓心位置由如下坐標變換公式求得：

5）將步驟3）中獲得的新的搜索窗口參數帶入到步驟2）中，繼續下一幀圖像的目標位置搜索。endprint

2 實驗結果與分析

本實驗是在配置為Intel酷睿雙核i5-2450M（2.5GHz）內存為1G的計算機上用Visual Studio 2010編程實現的。

所用移動機器人為自搭的簡易四輪全自主移動機器人，攝像頭為百腦通高清網絡攝像頭。

圖1所示為移動機器人跟蹤移動乒乓球在不同位置的四幅圖像，圖像大小均為640×480像素。表1是四幅跟蹤圖像中乒乓球的圖像像素坐標位置。由圖1和表1可知本文算法運用在移動機器人上能夠對簡單室內環境中的球體進行跟蹤識別，識別精度高。

表1 移動乒乓球球心圖像像位置

圖像 a b c d

圓心坐標 （328，377） （304，379） （239，377） （347，409）

圖2為只采用隨機Hough變換對同樣一張圖像的檢測結果，圖3為用CamShift算法結合Hough變換識別小球的圖像。由圖2和圖3可知僅采用隨機Hough變換對球形物體跟蹤會引入大量無效累積，且對背景稍微復雜的圖像檢測效果不理想。而用本文提出的球體檢測算法可以達到比較好的檢測效果。

圖2 僅用隨機Hough變換檢測結果 圖3 本文算法檢測結果

3 結束語

本文研究了CamShift算法與隨機Hough圓變換的主要原理，融合了兩種算法的優點，提出一種基于CamShift算法與隨機Hough圓變換結合的算法來跟蹤識別球形目標的方法。在室內運動球體的跟蹤實驗中，此方法運行效果良好，跟蹤識別精度高，實時性強。但還存在對于有顏色干擾和稍復雜的背景下跟蹤效果不夠理想，這還需在后續研究中進一步改進和完善。

參考文獻

[1]Gary R B. Real time face and object tracking as a component of a perceptual user interface[A]. Proceedings of 4th Workshop on Applications of Computer Vision[C]. Princeton， USE： IEEE， 1998： 214-219.

[2]Cheng Yizong. MeanShift mode seeking and clustering[J].IEEE Transaction on Pattern Analysis and Machine Intelligence， 1995， 17（8）： 790-799.

[3]XU L， OJA E. A new curve detection method： Randomized Hough Transform（RHT）[J]. Pattern Recognition Letters，1990， 11（5）： 331-338.

[4]劉延杰，賴日飛，等.基于改進隨機Hough變換的快速中心檢測方法[J].納米技術與精密工程，2011，9（4）：298-304.

[5]付琰，盧榮勝，等.基于重要性采樣的隨機Hough變換圓檢測算法[J]. 電子測量技術，2012，35（5）：45-48.

[6]Christoper Hollit. A convolution approach to the circle Hough transform for arbitrary radius[J].Machine Vision and Applications， 2013，24（4）：683-694.

作者簡介

張晨（1991-），男，江蘇泰州人，大學本科生，機械電子工程專業。

通信作者：王紅茹（1979-），女，河南南陽人，講師，博士，研究方向：智能機器人技術。endprint

2 實驗結果與分析

本實驗是在配置為Intel酷睿雙核i5-2450M（2.5GHz）內存為1G的計算機上用Visual Studio 2010編程實現的。

所用移動機器人為自搭的簡易四輪全自主移動機器人，攝像頭為百腦通高清網絡攝像頭。

圖1所示為移動機器人跟蹤移動乒乓球在不同位置的四幅圖像，圖像大小均為640×480像素。表1是四幅跟蹤圖像中乒乓球的圖像像素坐標位置。由圖1和表1可知本文算法運用在移動機器人上能夠對簡單室內環境中的球體進行跟蹤識別，識別精度高。

表1 移動乒乓球球心圖像像位置

圖像 a b c d

圓心坐標 （328，377） （304，379） （239，377） （347，409）

圖2為只采用隨機Hough變換對同樣一張圖像的檢測結果，圖3為用CamShift算法結合Hough變換識別小球的圖像。由圖2和圖3可知僅采用隨機Hough變換對球形物體跟蹤會引入大量無效累積，且對背景稍微復雜的圖像檢測效果不理想。而用本文提出的球體檢測算法可以達到比較好的檢測效果。

圖2 僅用隨機Hough變換檢測結果 圖3 本文算法檢測結果

3 結束語

本文研究了CamShift算法與隨機Hough圓變換的主要原理，融合了兩種算法的優點，提出一種基于CamShift算法與隨機Hough圓變換結合的算法來跟蹤識別球形目標的方法。在室內運動球體的跟蹤實驗中，此方法運行效果良好，跟蹤識別精度高，實時性強。但還存在對于有顏色干擾和稍復雜的背景下跟蹤效果不夠理想，這還需在后續研究中進一步改進和完善。

參考文獻

[1]Gary R B. Real time face and object tracking as a component of a perceptual user interface[A]. Proceedings of 4th Workshop on Applications of Computer Vision[C]. Princeton， USE： IEEE， 1998： 214-219.

[2]Cheng Yizong. MeanShift mode seeking and clustering[J].IEEE Transaction on Pattern Analysis and Machine Intelligence， 1995， 17（8）： 790-799.

[3]XU L， OJA E. A new curve detection method： Randomized Hough Transform（RHT）[J]. Pattern Recognition Letters，1990， 11（5）： 331-338.

[4]劉延杰，賴日飛，等.基于改進隨機Hough變換的快速中心檢測方法[J].納米技術與精密工程，2011，9（4）：298-304.

[5]付琰，盧榮勝，等.基于重要性采樣的隨機Hough變換圓檢測算法[J]. 電子測量技術，2012，35（5）：45-48.

[6]Christoper Hollit. A convolution approach to the circle Hough transform for arbitrary radius[J].Machine Vision and Applications， 2013，24（4）：683-694.

作者簡介

張晨（1991-），男，江蘇泰州人，大學本科生，機械電子工程專業。

通信作者：王紅茹（1979-），女，河南南陽人，講師，博士，研究方向：智能機器人技術。endprint

2 實驗結果與分析

本實驗是在配置為Intel酷睿雙核i5-2450M（2.5GHz）內存為1G的計算機上用Visual Studio 2010編程實現的。

所用移動機器人為自搭的簡易四輪全自主移動機器人，攝像頭為百腦通高清網絡攝像頭。

圖1所示為移動機器人跟蹤移動乒乓球在不同位置的四幅圖像，圖像大小均為640×480像素。表1是四幅跟蹤圖像中乒乓球的圖像像素坐標位置。由圖1和表1可知本文算法運用在移動機器人上能夠對簡單室內環境中的球體進行跟蹤識別，識別精度高。

表1 移動乒乓球球心圖像像位置

圖像 a b c d

圓心坐標 （328，377） （304，379） （239，377） （347，409）

圖2為只采用隨機Hough變換對同樣一張圖像的檢測結果，圖3為用CamShift算法結合Hough變換識別小球的圖像。由圖2和圖3可知僅采用隨機Hough變換對球形物體跟蹤會引入大量無效累積，且對背景稍微復雜的圖像檢測效果不理想。而用本文提出的球體檢測算法可以達到比較好的檢測效果。

圖2 僅用隨機Hough變換檢測結果 圖3 本文算法檢測結果

3 結束語

本文研究了CamShift算法與隨機Hough圓變換的主要原理，融合了兩種算法的優點，提出一種基于CamShift算法與隨機Hough圓變換結合的算法來跟蹤識別球形目標的方法。在室內運動球體的跟蹤實驗中，此方法運行效果良好，跟蹤識別精度高，實時性強。但還存在對于有顏色干擾和稍復雜的背景下跟蹤效果不夠理想，這還需在后續研究中進一步改進和完善。

參考文獻

[1]Gary R B. Real time face and object tracking as a component of a perceptual user interface[A]. Proceedings of 4th Workshop on Applications of Computer Vision[C]. Princeton， USE： IEEE， 1998： 214-219.

[2]Cheng Yizong. MeanShift mode seeking and clustering[J].IEEE Transaction on Pattern Analysis and Machine Intelligence， 1995， 17（8）： 790-799.

[3]XU L， OJA E. A new curve detection method： Randomized Hough Transform（RHT）[J]. Pattern Recognition Letters，1990， 11（5）： 331-338.

[4]劉延杰，賴日飛，等.基于改進隨機Hough變換的快速中心檢測方法[J].納米技術與精密工程，2011，9（4）：298-304.

[5]付琰，盧榮勝，等.基于重要性采樣的隨機Hough變換圓檢測算法[J]. 電子測量技術，2012，35（5）：45-48.

[6]Christoper Hollit. A convolution approach to the circle Hough transform for arbitrary radius[J].Machine Vision and Applications， 2013，24（4）：683-694.

作者簡介

張晨（1991-），男，江蘇泰州人，大學本科生，機械電子工程專業。

通信作者：王紅茹（1979-），女，河南南陽人，講師，博士，研究方向：智能機器人技術。endprint