An Adaptive Kernel Bandwidth Mean-Shift__Target Tracking Algorithm

An Adaptive Kernel Bandwidth Mean-Shift Target Tracking AlgorithmChangyou Wang1. College of Mathematics and Physics Chongqing University of Posts and Telecommunications Chongqing 400065 P.R. China2. Key Laboratory of Industrial Internet of Things &Networked Control, Ministry of EducationChongqing 400065 P.R. ChinaHaiqiang ZhangCollege of AutomationChongqing University of Posts and Telecommunications Chongqing 400065 P. R. ChinaFuping YangCollege of Computer Science and Technology Chongqing University of Posts and TelecommunicationsChongqing 400065, ChinaAbstract—As the traditional Me an-Shift tracking algorithm fix the bandwidth of kernel functionˈit can not effectively track the target when the scale of tracking target has a distinct changeˊIn re sponse to this shortage, a targe t tracking algorithm which combines target detection and contour tracking with Mean- Shift tracking algorithm is proposed. It use s the contour information of the real-time for the tracking target and updates adaptability th e k e rn e l bandwidth of M e an-Shift tracking algorithm. Expe rime ntal re sults show that the improve d algorithm has a good adaptability when the scale of the target changeˊKeywords-mean-Shif t; t arge t t racking; con t our t racking; adaptive bandwidthI.INTRODUCTIONTarget tracking has attracted a growing number of researchers in the research direction of computer vision. It has been widely used in many fields of intelligent human-computer interactionˈmedical diagnostics, intelligent robotics, video surveillance etcˊThe focus of target tracking is how to track the target in the video sequence in a stable and effective way. Thus, a practical application of the tracking system can be able to adapt in real-time to changes in appearance that occurs to the target due to a variety of sportsˊAt presentˈthere is no systematic approach to solve the tracking window problem which can automatically adjust the size of the tracking windowˊMean-Shift [1, 2] algorithm as an efficient pattern matching algorithm does not require exhaustive search. It has been successfully applied in target tracking algorithm which requires higher performance in real-time. The size of the bandwidth of kernel function plays an important role in Mean-Shift tracking algorithm because it not only affects the weight of each pixel value but also reflects the shape and size of the targetˊUnder normal circumstancesˈbandwidth of kernel function is given in selecting the target in the first frame and remains unchanged throughout the tracking processˊHoweverˈwhen the target scale changesˈespecially the scale of target become larger and beyond the scope of the kernel bandwidth, fixed kernel function often lead to the loss of target tracking. In order to solve this problem, many domestic and foreign scholars has done a lot of researches and have got some meaningful methods and the conclusions. Comaneci [3]propose the tracking window width plus or minus 10% increment for subsequent frames target trackingˈand select the larger Bhattacharyya coefficient corresponding to the kernel bandwidth as the best kernel bandwidth. The experiment results show that the method has a good target tracking performance in the reducing size of the targetˊHuimin Qian [4] proposed to introduce the amount of information measure in multi-scale image into the moving target trackingˈand update the scale by using image information and the relationship between the measurement scales. Howeverˈthe calculation of the amount of information of the image is time-consumingˊIt lost the real-time of the tracking algorithmˊIn order to solve the inadaptability problem when the target dimension changes in the traditional Mean-Shift tracking algorithm, an improved Mean-Shift tracking algorithm is proposed by using the knowledge of the object detection and contour tracking. Experimental results show that the proposed algorithm has a good bandwidth adaptabilityˊII.THE MEAN-SHIFT TRACKING PROCEDUREMean-Shift is an image feature analysis method based on Kernel density estimation[5]ˊIn target trackingˈMean-Shift tracking algorithm uses the histogram information of the image color as the eigenvalue of the entire search and the gradient optimization method is used to achieve the fast targeting orientation as well as the Bhattacharyya coefficient is acted as the similarity function of the target template and candidate target to complete the matching of characteristics. A.Target Model and Target CandidatesIn the target tracking, the target is usually defined as a rectangular or circular regionˊAssume {}1,2,...,i i nx=be the pixel locations of the target modelˈand the target regioncenter isxˈthe number of the eigenvalue bin is mˊHenceˈthe probability density of in eigenvalue u=1,2,,m"of the target template can be defined as()21niiuix xq C k b x uhδ∧=§·−=−ªº¨¸¬¼¨¸©¹¦ˈ(1)2012 International Conference on Control Engineering and Communication Technologywhere()x k is kernel function ˈits purpose is to set theweight to the target template region of pixels ˈand to set abigger weight near the center of the target template ˊ The role of0i x x h− in the function ()x k is to eliminate theimpact of the calculation of the different scale for target and to get the target region normalized ˊ()x δis the Kronecker deltafunction. The role of ()i b x u δ−ªº¬¼ is to determinewhether the color values of pixel i x belong to the u -thbin in the target region. The value is 1 if it belongs to u -th bin while the value is 0 if it doesn’t ˊThe normalizationconstantC is derived by imposing the condition11m uu q∧==¦.Thus, we have2011nii C x x k h ==§·−¨¸¨¸©¹¦ˊ ˄2˅Set the target region contained in the second frame and aftereach frame of moving target as a candidate region ˊLet{}1,2,...,hi i nx =be the pixel locations of the candidateregion ˊIts center coordinate is in the current frame ˊThe probability density of the target candidate in eigenvalue u=1,2,,m "is given by()()21hn ih i u i y x p y C k b x u h δ∧=§·−=−ªº¨¸¬¼¨¸©¹¦ˈ ˄3˅ where211hh n ii C y x k h ==§·−¨¸¨¸©¹¦ is the normalizationconstant ˊB. The similarity function of based on the BhattacharyyaCoefficientThe Bhattacharyya coefficient that represents the similar degree between the target candidates and the target template can be defined as()()ˆˆˆ,mu y p y q ρρ===ªº¬¼ˈ ˄4˅ The value of()y ρ∧is between 0 and 1. The similar degreebetween two models will be higher if the value of()ˆy ρis greater ˊThe candidate region whose()ˆp y value is greatestamong the candidate regions is act as the target position of thecurrent frame ˊC. Target LocationIf the target need to be positioned in the detected frame, the value of()y ρ∧should be maximum ˊThe search for thenew target location in the current frame starts at the estimatedlocation 0y of the target in the previous frame ˊThus ˈthe color probabilities (){}0 1...u u mp y ∧= of the target candidate atlocation0y ∧in the current frame have to be computed first ˊUsingTaylor expansion around the values ()0p y ∧ˈthe Bhattacharyya coefficient is approximated as()211,22hm u n h i i i p y q C y x wk h ρ∧∧==ªº≈«»¬¼§·− ¨¸¨¸©¹¦ˈ ˄5˅where()mii u w b x u ==−ªº¬¼ˊ˄6˅ Thus ˈto maximize the distance (4)ˈthe second term in equation (5) has to the maximized, with the first term being independent of y . Calculation of Man-Shift vector derives the new location of the target211201hhn i i i i n i i i y x x w g h y y x w g h ∧=∧∧=§·−¨¸¨¸¨¸©¹=§·−¨¸¨¸¨¸©¹¦¦ˈ ˄7˅ where()()g x k x ′=−ˊ Mean-Shift algorithm is from0y ∧to the lager color direction of the two models ˊIII. KERNEL WITH ADAPTIVE BANDWIDTHTracking window scale plays a key role in the iterative process of target tracking ˊThe tracking results will be affected if the tracking window is too large or the background area in the tracking window is too much [6]. However, the tracking window can not effectively track the target and the trackingtarget will get lost if the tracking window or the target information is too small. A way of detecting moving targets and tracking contour information is introduced to solve the problems caused by the fixed window ˊA. Moving Target Detection and Contour InformationThe commonly used methods for movement of the target detection are inter-frame difference method [7] and the background subtraction method [8]ˊInter-frame method is to obtain the outline of a moving target by difference calculation of two adjacent frames in video sequence. The main idea is based on the difference of the gray pixels to the two frames for a tiny time interval ˈand then to use a threshold method to extract the moving regions in an image. It can describe as ˖()()()()()0,,,,,,1,,,,f x ytf x yt t M x yt f x yt f x yt t ττ­−−Δ≤°=®−−Δ>°¯ˈ ˄8˅where t Δis the time interval while(),,f x y t and(),,f x y t t −Δ are images of t and t t −Δ respectively.If the difference of the two images corresponding to the absolute value of the pixel gray level is greater than thethreshold τˈit indicates that the pixel is moving foreground ˈand its value is therefore set as 1. Otherwise it indicate a static background and its value is 0ˈand we can get the binaryimages (),,M x y t ˊInter-frame difference method has thefollowing advantages ˖the algorithm is simple; the program design complexity is low; it’s less sensitive to light scene changes; it can adapt to a dynamic environment and has a better stability ˊIn video sequences, background difference and inter-frame difference method is used as inspiration ˈand two frame difference image and background difference imageis directly operated in dynamic sequence images, and then thesports results is got from the binary processing of the results ˊThis increases the weight of the target information while suppressing the effect of a static background. The motion detection image that is got contained more information of the target. Thus, the moving target can be separated from the background image. Finally we can obtain the video image sequences of the presence or absence ofmovement of binary image ˊTherefore ˈwe adopt inter-frame method for target detection in the target tracking ˊAfter getting images of the binary image ˈcontour information is obtained according to contour trackingalgorithm for the moving object ˊThe basic idea of contourtracking algorithm is as follows: Firstly, to find the targetobject contour pixels according to some strict "detectioncriterion". Then, to find out the other pixels on the targetaccording to some of the characteristics of these pixels withcertain "tracking criterion"ˊThe first is to find the firstboundary pixels. The "tracking criteria" we use are ˖to have a sequential search from left to right and then from top tobottom. The first black point must be the most down-left sideof the boundary point, which is recorded as A. Starting withthis boundary point starting, we hypothesize to have found allthe boundary points through clockwise rotation around the entire image a circle ˊBecause the boundary is continuous ˈ every boundary point can be represented by the way of using the angle of the previous boundary point of the boundary point ˊSo we can use the following "tracking criterion"˖starting from a boundary point ˈwe can define the initial search direction which is along the left direction. If the upper left point is a black point ˈit can be defined as the boundary point ˈotherwise the search direction will be turned 45 degrees clockwise ˈand without stop until the first black point is found ˊThen the black point is taken as the new boundary point, turning 90 degrees counter clockwise in the current search direction. Using the same method to keep on searching the next black point until you return to the initial boundary point A ˊB. Adap t ive kernel bandwid t h of Mean-Shif t t racking algorithmBased on the discussion of the previous section ˈwe find the extreme points of the four directions of top, bottom, left, right contour pixels respectively. These four points were setto ˖the leftmost pixel (),l l l P x y ˈthe rightmost pixel (),r r r P x y ˈthe top pixel (),t t t P x y ˈthe bottom pixel (),b b bP x y ˊWe have a tracking the target current scale afterthe four boundary points are determined ˊHere ˈlet w isthe width of the tracking target and h is the height. Thus, wehave ˖ r l t bw x x h y y =−­®=−¯ˈ (9) By formula (9)ˈwe determine the scale of the tracking target. At the meantime, we also get the bandwidths on the Mean-Shift iteration algorithm in the x direction and y direction ˈrespectively ,2.2x y w h h h ­=°®=°¯ (10) Steps for updating kernel bandwidth algorithm are asfollows ˖ a) Initialize frame S=0ˈand manually select the track window ˊ b) Load a frame image S ˈcalculate the current frame target dimension center point P by a frame image before the selected tracking or target tracking window ˊ c) Calculate target contour in the current frame moving ˊ d) Select the contour of the tracking target which contains point P ˊe)Update the bandwidth of kernel function in currentframe for the Mean-Shift iteration algorithm accordingto formula (10)ˊf)For Mean-Shift iteration, find the current frame of targettracking and continue to track next frame of the target.If tracking video is not over, return Step bˈotherwiseStopˊIV.EXPERIMENTSWe analyze the experimental results of the different image sequences of the moving vehicle in the proposed tracking algorithmˊThe color images in each video frame image are bitmaps formatsˈand the color image size is 384*288 pixelsˊThe experiments process is performed on the Visual C++6.0 platform with the Inter Core 2.93GHzˊTheprogramming of the experiment uses the open source computer vision library OpenCVˊFigˊ1 shows this algorithm of vehicle tracking resultsˈFigˊ2 shows the fixed kernel bandwidth Mean-Shift tracking algorithm of vehicle tracking resultsˊFigˊ1 and Figˊ2 selected the video 9 frameˈ27 frameˈ53 frameˈ71 frameˈ93 frame and 108 frame to compare with the two algorithm of tracking effectˊBy the six frames contrastˈwe can find the tracking window of 9 frameto 27 frame in Figˊ2 remained relatively complete tracking when the car body dosen not change much. From 53 frame to 108 frameˈthe car body gradually become larger. We can see that the fixed kernel bandwidth algorithm only track part of the bodyˈand the tracking window deviates from the center of the car bodyˊFigˊ1 with this algorithm clearly shows the track window can track better with bigger the car body grow biggerˊThe analysis above indicates this algorithm proposed in this paper is successful.Figure 1.The car tracking results of the proposed algorithmˊThe car tracking results of the Mean-Shift algorithm with fixedkernel bandwidthˊV.CONCLUSIONThis paper proposes a target tracking algorithm which combines detection and contour tracking with Mean-Shift tracking algorithm. Experiments show that the algorithm proposed in this paper can effectively track the target whose scale changesˊACKNOWLEDGMENTThis work is supported by Science and Technology Project of Chongqing municipal education committee (Grant nos. kJ110501, KJ120520) of China.REFERENCE[1]K. Fukanage and L. D. HostetlerˈĀThe estimation of the gradient of adensity functionˈwith applications in pattern recognition,” IEEE Trans on Information TheoryˈV olˊ 21ˈppˊ32-40ˈJan 1975ˊ[2]Y. ChengˈĀMean shiftˈmode seeking and clusteringˈāIEEE Trans onPattern Analysis and Machine IntelligenceˈV olˊ17ˈppˊ790-799ˈAug 1995ˊ[3]D. ComaniciuˈV. Ramesh and P. Meerˈ“Real-time tracking ofnon-rigid objects using Mean Shiftˈ” Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern RecognitionˈNew York˖IEEE Pressˈ2000ˈppˊ142-149ˊ[4]H. M. QianˈY. B. Mao and Z. Q. Wangˈ“Mean Shift Tracking withSelf-updating Tracking Windowˈ” Journal of Image and GraphicsˈV olˊ12ˈppˊ245-249ˈFeb 2007ˊ[5] D. Comaniciu and P. MeerˈĀMean Shift˖A Robust Approach TowardFeature Space AnalysisˈāIEEE Trans on Pattern Analysis and Machine IntelligenceˈV olˊ24ˈpp. 603-619, May 2002ˊ[6]N. S. PengˈJ. YangˈZ. Liu and F. C. Zhang, “Automatic Selection ofkernel-Bandwidth for Mean-Shift Object Trackingˈ”Journal of SoftwareˈV olˊ16ˈppˊ1542-1550ˈSep 2005ˊ[7]O. NaoyaˈĀA statistical approach to background subtraction forsurveillance systemsˈāProceedings of English IEEE International Conference on Computer Vision[C], V ancouver, BC, Canadaˈppˊ481-486ˈ 2001ˊ[8]D. R. MageeˈĀTracking multiple vehicles using foregroundbackground and motion modelsˈāImage and Vision ComputingˈV olˊ22ˈppˊ143-155ˈFeb 2004ˊ。