# Study of Clustering Algorithms in Object Tracking and Image Segmentation

Authors: Yongfeng Xing; Luo Zhong; Xian Zhong
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Mean Shift is a kind of clustering algorithm, which is mostly used for target tracking, image segmentation, etc. In order to solve the problem that image information is not effectively utilized because of unclear traffic video images and random jitter between image sequences, this paper has studied how to achieve stability of traffic video images and proposed an improved Mean Shift algorithm about how to conduct object centroid registration in compensation for the deviations in space localization and, on this basis, how to select kernel window width to eliminate the errors in scale positioning. This algorithm gets the tracking effect and computation analysis of improved Mean Shift from the perspective of applications, removes or relieves the impact motion has on imaging, improves the quality of the video image information obtained, automatically adjusts the size of window according to the scale changes of moving object in the image, and effectively enhances the stability and real time of object tracking. Besides, in the postprocessing stage, the superpixel based on the Mean Shift algorithm is applied to further optimize the segmentation result; it is a popular mode-seeking clustering algorithm, which makes Mean Shift method ideal on low-dimensional applications such as image segmentation. Finally, we show promising results for remote sensing image segmentation.


---

## Body

## 1. Introduction

Object tracking refers to the instant velocity of pixel motion of moving object in observation and imaging plane, which makes use of time-domain changes and correlation of image sequence pixel intensity to pin down the motion of the position of each pixel; in other words, it reflects the relationship between the changes of image grayscale over time and the structure and motion of the object in the scene [1]. Traffic video object tracking has already become a hot but difficult topic in the researches about computer vision in recent years. As imaging devices are affected by postures and vibrations, the images to be obtained will not be clear and there will be random jittering between image sequences, thus severely affecting effective utilization of image information [2]. Traffic video image stabilization technique will provide a relatively stable coordinate system for the measurement plane of the instrument in order to ensure accurate measurement results, reduce the possibility of blurring images caused by involuntary motion, and improve imaging quality [3]. Video object tracking now has already been widely applied in a variety of fields, such as intelligent transportation system and video surveillance, so it is of great significance to study an object tracking algorithm with good real time, strong robustness, and high accuracy. In video image sequences, there are two kinds of motion: one is global motion, namely, the change of the whole image caused by the changes in the positions or parameters of cameras, and the other is local motion, i.e., the change of local image caused by the motions of the object in the scene [4]. Both purposeful and unnecessary motions of cameras will lead to global motion of image sequences, and image stabilization is to eliminate the unnecessary camera motion. Therefore, the global motion of image sequences requires to be estimated. Among object tracking algorithms, such as deep learning and correlation filtering, Mean Shift algorithm has attracted in-depth study and close attention at home and abroad because of its easy implementation and good real time [5]. Correlation tracking algorithms have been widely used in tracking systems for their simple and practical characters. Correlation filter based on object tracking method has been widely used for its high efficiency. However, reducing model drifting while achieving both high robustness and fast scale estimation is still an open problem. Different from the trend of deep learning in the visual field such as detection and recognition, the application of it in the field of object tracking is not good yet. The main problem is that the lack of large datasets of deep learning causes slower speed in object tracking tasks than that of the Mean Shift algorithm.Semantic segmentation is a classic and fundamental topic in computer vision. It is a pixel-level classification task, which plays an important role in many fields such as autonomous driving, video surveillance, geographic information systems, and medical image analysis [6].The special contributions of this paper include the following:(i)
To analyze and study the stability of traffic video images, eliminate unnecessary camera motion, and obtain smooth object motion of camera so as to achieve image stabilization and smooth camera motion(ii)
To introduce common object tracking algorithms and procedures, study the difficulties and performance index of object tracking technology, and focus on the analysis and research of Mean Shift object tracking algorithm(iii)
To study the descriptions of object model and candidate model of traffic video image and weigh the difference or similarity between these two kinds of models. Based on the object localization in traffic video image, search the real position of the object in the current frame(iv)
Based on the in-depth study of the principle of related object tracking algorithms, propose an improved Mean Shift object tracking algorithm, select different video sequences, conduct detailed analysis and comparison of algorithm performance through experiment, and verify their strengths, weaknesses, and application scope(v)
Experimental results on widely used high-resolution remote sensing datasets for semantic segmentation tasks, ISPRS Vaihingen, demonstrate competitive performance obtained by the proposed methodology compared to other studied approaches


## 2. Related Work

With the extensive applications of object tracking techniques, the requirements on object tracking algorithms may be different; in general, there are three basic requirements: accuracy, robustness, and real time. Accuracy includes accuracy on object detection and on object tracking, and it is an important index in the application of surveillance [7]. Image stability is constituted by global motion estimation, motion smoothness, and image reconstruction, and it defines the instant rate of gray change in specific coordinate point in the plane of 2D image as vector. Object tracking refers to the apparent motion of image grayscale mode. It is a 2D vector field, and the information it contains is the vector information of instant motion velocity of each pixel point. In object tracking, each pixel has a motion vector; so it can reflect the motion between neighboring frames. In the recognition of behaviors of the object in traffic video image, robustness is to maintain continuous and stable tracking on the moving object under different external factors [8]. This is also a significant index of surveillance and tracking; meanwhile, as surveillance system usually needs to automatically and constantly monitor the object for a long time, its ability against bumpy roads and noises requires to be improved. For those systems in which real-time and high-speed surveillance is required, computation speed, i.e., real-time, is extremely important; therefore, it appears to be particularly important for how to select effective algorithm to reduce losses and improve antijamming capability of object tracking [9–11].The concept of Mean Shift was firstly proposed by Fukunaga and Hostetler in an article concerning estimation of probability density gradient function in 1975. It is a nonparametric estimation algorithm, and it searches the peak of distribution along the ascent direction of probability gradient and defines a cluster of kernel functions, the deviation of which makes different contributions to Mean Shift vector over different distances between the sample and the deviated point [12]. Besides, it also sets a weight coefficient, making different sample points have different importance. This has expanded the range of application of Mean Shift. As research is deepened about Mean Shift, it has evolved into a process from a vector and The Mean Shift algorithm generally refers to an iterative process; in other words, firstly, it computes the Mean Shift of the current point, according to which, it moves this point; then, it takes the moved point as the benchmark, continues to compute the Mean Shift, and repeats the above steps in iteration until it meets certain conditions and ends. The Mean Shift algorithm through the kernel function density estimation method of nonparametric density estimation converges the mode centroid of density along the direction of density gradient quickly and effectively [13]. If Mean Shift algorithm satisfies certain conditions, it can converge to the nearest stable centroid of probability density function; so, the Mean Shift algorithm can be used to detect the mode in probability density function. Some scholars have combined scale space with Mean Shift to solve object tracking in real-time change of object size, but its speed is not ideal enough. The Mean Shift algorithm does not have much computation and it can perform real-time tracking when the object region is known. It uses histogram model of kernel function, and it is not sensitive to edge occlusion, object rotation, deformation, and background motion. And as the window width remains the same in the tracking process, the frame region will not expand (or shrink) over the expansion (or shrinkage) of the object. When the object moves fast, the tracking effect is not good with a lack of histogram features in description of object color features and space information [14–16].


## 3. Stability of Traffic Video Image

Motion smoothness is to remove unnecessary camera motion and obtain smooth camera object motion so as to achieve image stabilization. Generally, take the estimated motion parameters of the camera as the noisy data of object motion parameters and use low-pass filter to get rid of high-frequency noises in camera motion parameters so as to achieve the purpose of smooth camera motion.After completing motion smoothness, it can perform calibration transformation on every frame of image in the video according to the difference between the preliminarily estimated camera motion parameters and the smoothed camera motion parameters so as to reconstruct stable video sequences.(1)
First, preprocess the image data and produce gray coding bit plane from standard binarization. Make thetth image in the K–bit gray image sequence as(1)ftx,y=aK−12K−1+aK−22K−2+⋯+a020The bit plane of this image is represented by the method from the least significant bitb0tx,y to the most significant bit b7tx,y. The 8-bit gray coding can be provided by the following formula:
(2)gK−1=aK−1,gk=akak+1,0≤k≤K−2,in which ak is the standard binary coefficient. In this algorithm, gray coding is very important and it makes the next motion estimation possible as this module divides most useful image information coding into several planes and uses one single bit plane for motion estimation. After gray coding, a tiny change in grayscale will lead to correspondingly uniform changes in the binary digit which represents intensity. Therefore, an extremely significant Boolean binary operation can be used to compare the gray coding bit plane of the previous image and the current image.
(2)
Use Boolean operation for the motion estimation in local region, namely, self-motion estimation. Make the error operator to be minimized as(3)εm,n=1W2∑∑gktx,ygkt−1x+m,y+n,−p≤m,n≤p,in which W is the slider used for search and p is the number of pixels to be searchedBy minimizing this error operator, the value ofm,n obtained represents the self-motion vector. Then, process these 4 self-motion vectors and the previous global motion vector with mean operator and obtain the current global motion vector estimation Vgt.Use filter for global motion estimation, fusion, and motion compensation. Then, get this global motion estimation through a specially designed filter, which can preserve the conscious motion of camera, such as conscious translation, and which can also remove the useless high-frequency motion. Finally, the filtered estimation result can make the compensation by moving the current frame by pixels of an integer value along the opposite direction of the motion.


## 4. Implementation of Mean Shift Algorithm

### 4.1. Kernel Function

Definition of kernel function: X represents a d-dimensional Euclidean space and x is a point in this space, which is represented by a column vector. The mode of x is x2=xTx. R represents the field of real numbers. If there is a section function k:0,∞⟶R in a function K:X⟶R, namely,
(4)Kx=kx2,and if the following conditions are satisfied:
(1)
k is nonnegative(2)
k is nonincreasing, namely, if a<b, then ka≥kb(3)
k is sectionally continuous and ∫0∞krdr<∞Then, the functionKx is called as Kernel function.In Mean Shift, the following three kinds of Kernel functions are very frequently used.(a)
Uniform kernel(5)KUx=cx≤1,0otherwise(b)
Normal kernel(6)KNxc⋅exp112x2(c)
Epanechnikov kernel(7)KEx=c1−x2x≤1,0otherwiseThese three kinds of Kernel functions are as follows [17], as shown in Figure 1.Figure 1
Three kinds of kernel functions.
(a)
Uniform kernel(b)
Normal kernel(c)
Epanechnikov kernel


### 4.2. Mean Shift Vector

It can be seen from Formula (3) that the sampling points falling into Sh make the same contribution to the computation of the final Mhx whether it is close or far away from x. However, we all know that generally speaking, the closer the sampling points are away from x, the more significant they are to estimate the statistical characteristics surrounding x. Therefore, we introduce the concept of kernel function and when computing Mhx, the impact of distance can be taken into consideration; in the meanwhile, we can also suppose that among all these sampling points xi, they are significant in different ways, so, we have introduced a weight coefficient for every sample.In this way, we can expand the basic Mean Shift form into(8)Mx≡∑i=1nGHxi−xwxixi−x∑i=1nGHxi−xwxi,in which Gx is a unit kernel function; H is a positive definite and symmetric d×d matrix, and we usually call it window width matrix; and wxi≥0 is a weight given to the sampling point xi, GHxi−x=H−1/2GH−1/2xi−x.In practical applications, the window width matrixH is generally restricted to a diagonal matrix H=diagh12,⋯,hd2 or even simply directly proportional to unit matrix, i.e., H=h2I. As the latter form only needs to confirm a coefficient h, Formula (8) can also be written as follows:
(9)Mhx≡∑i=1nGxi−x/hwxixi−x∑i=1nGxi−x/hwxi.We can see that if all sampling pointsxi satisfy the following conditions:
(1)
wxi=1(2)
Gx=1ifx<1,0ifx≥1Mean Shift vectorMhx is the normalized probability density gradient and iterative Mean Shift algorithm will converge to a stable centroid of probability density function [18].


### 4.3. Probability Density Gradient

For a probability density functionfx, it is known that there are n sampling points xii=1,⋯,n, in d-dimensional space, and then, the kernel function estimation (also called as Parzen windowing estimation) of fx is as follows:
(10)f^x=∑i=1nKxi−x/hwxihd∑i=1nwxi,in which wxi≥0 is a weight given to sampling point xi and Kx is a kernel function and it satisfies∫kxdx=1.Besides, the section function of the kernel functionKx is kx and it makes
(11)Kx=kx2.The negative derived function ofkx is gx, namely, gx=−k′x, and its corresponding kernel function is as follows:
(12)Gx=gx2.The estimation of gradient∇fx of probability density function fx is
(13)∇^fx=∇f^x=2∑i=1nx−xik′xi−x/h2wxihd+2∑i=1nwxi.According to the definition above,gx=−k′x and Gx=gx2. So, the formula above can be written as
(14)∇^fx=2∑i=1nxi−xGxi−x/h2wxihd+2∑i=1nwxi=2h2∑i=1nGxi−x/hwxihd∑i=1nwxi∑i=1nxi−xGxi−x/h2wxi∑i=1nGxi−x/hwxi.The part in the second square bracket in the right hand of the above formula is the Mean Shift vector as defined in Formula (9), and the part in the first square bracket is the estimation of probability density function fx with Gx as the kernel function, which is marked as f^Gx. Then, f^x as defined in Formula (10) is marked as f^Kx, so Formula (12) can be changed into
(15)∇^fx=∇f^Kx=2h2f^GxMhx.It can be seen from Formula (13) that
(16)Mhx=12h2∇f^Kxf^Gx.Formula (16) shows that the Mean Shift vector Mhx computed and obtained at point x with kernel function G is proportional to the normalized gradient of probability density function f^Kx estimated with kernel function K and the normalization factor is the probability density of point x estimated with kernel function G. Therefore, Mean Shift vector Mhx always points to the direction the probability density increases the most.The Mean Shift algorithm is an iterative step. In another word, it computes the Mean Shift of the current point. Then, this point is moved to this Mean Shift and it will become a new starting point. Continue to move until it satisfies the final conditions [19]. This process can be seen in Figure 2 below.Figure 2
Schematic diagram of the Mean Shift algorithm.
(a)(b)(c)(d)(e)(f)It can be seen from the above process that the Mean Shift is computed in the designated region. Move this point to the point of Mean Shift. Compute the new Mean Shift, and move it. Repeat this process until it meets the final conditions. Then, quit. In the Mean Shift algorithm, the most important key is to compute the Mean Shift of every point and then update the position according to the new Mean Shift.


### 4.4. Object Tracking Based on Mean Shift

The Mean Shift algorithm can initialize the object to be tracked by auto or semiauto methods. Semiauto is to manually designate the object region of interest in the initial frame while auto is to get the object region to be tracked through object detection method. Object region is the region where kernel function works, and its size is the window width (scale) of the kernel function. When the Mean Shift algorithm tracks the object, the object features usually choose color feature of the object. Real-time processing shall meet the requirement of low computation, and it can divide every subspace under certain color space intok equal regions, namely, k bins. The color histogram feature of the possible object region in the video image is the description of the candidate model. Generally, Epanechnikov function is chosen as the kernel function. Use the proper similarity function to compute the similarity of the candidate model and the object model, and use the maximum value of similarity function to get the Mean Shift vector, i.e., the shift of object in the current frame. The object will eventually converge to the real position after several iterations so as to achieve the purpose of tracking.


#### 4.4.1. Description of Object Model

Assume thatxii=1,2,⋯,n represents the n pixels in the object region and the coordinate of the object center point is x0; then, the probability distribution density of all pixel points in this object region is qu.
(17)q^u=C∑i=1nkxis−x0h2δbxis−u,in which kx is the kernel function and it is used to represent the weight of object color histogram. The closer it is to x0, the bigger the weight. h is the window width of the kernel function, and bx is the color feature of the object region xi. δx is a 1D delta function, and it is used to judge whether the index value of xi is equal to the feature value u, and its value is 1 when they are equal and otherwise, 0. C is the normalization constant.
(18)C=1∑i=1nkxi−x0/h2.


#### 4.4.2. Description of Candidate Model

The possible object region after the initial frame is the candidate region. Make its central position asy, and the pixels in the region are represented with xii=1,2,⋯,n. Compare the description of object model, and the probability density of the candidate model is as follows.The candidate object located iny can be described as
(19)p^uy=Ch∑i=1nhkxis−yh2δbxis−u,(20)Ch=1∑i=1nkxi−x0/h2.


#### 4.4.3. Similarity Function

Similarity function is used to measure the difference or similarity between the object model and the candidate object model. In the Mean Shift algorithm, Bhattacharyya coefficient is the similarity coefficient and it refers to the approximate computation of the overlapping of two statistical samples and it is used to measure the correlation of two groups of samples [19]. Therefore, object tracking can be simplified into the search for the optimal y to make p^uy most approximate to q^u.The distribution of the similarity betweenp^uy and q^u is measured by Bhattacharyya coefficient ρ^y, namely,
(21)ρ^y≡ρpy,q=∑u=1mpuyq^u.Perform Taylor expansion at pointp^uy^0 on Formula (21), and obtain
(22)ρpy,q≈12∑u=1mpy0qu+12∑u=1mpuyqupuy0.Bring Formula (19) into the formula, and get
(23)ρpy,q≈12∑u=1mpy0qu+Ch2∑i=1nwiky−xih2,in which
(24)wi=∑u=1mδbxi−uqupuy0.


#### 4.4.4. Object Localization

To search the real position of the object in the current frame, it is to find the largest candidate region. First, localize the object center in the previous frame as the object center of current frame and search the optimal matching region starting from this point. Make the center asy. Assume that various feature distribution densities of object candidate region are puyu=1,2,⋯,m and the coordinate of the central point of the object in the last frame is y0; then, the central position of the tracking object in the current frame is y1.
(25)y1=∑i=1mxiwigy0−xi/h2∑i=1mwigy0−xi/h2,in which gx=−k′x and wi is the weight.
(26)wi=∑u=1mqupuy0δbxi−u.Compute the value ofy1 through iteration. When the two neighboring iterative values are smaller than a certain threshold, the position in the current frame of the tracking object can be confirmed and the real position of the object can be found after several iterations.


## 4.1. Kernel Function

Definition of kernel function: X represents a d-dimensional Euclidean space and x is a point in this space, which is represented by a column vector. The mode of x is x2=xTx. R represents the field of real numbers. If there is a section function k:0,∞⟶R in a function K:X⟶R, namely,
(4)Kx=kx2,and if the following conditions are satisfied:
(1)
k is nonnegative(2)
k is nonincreasing, namely, if a<b, then ka≥kb(3)
k is sectionally continuous and ∫0∞krdr<∞Then, the functionKx is called as Kernel function.In Mean Shift, the following three kinds of Kernel functions are very frequently used.(a)
Uniform kernel(5)KUx=cx≤1,0otherwise(b)
Normal kernel(6)KNxc⋅exp112x2(c)
Epanechnikov kernel(7)KEx=c1−x2x≤1,0otherwiseThese three kinds of Kernel functions are as follows [17], as shown in Figure 1.Figure 1
Three kinds of kernel functions.
(a)
Uniform kernel(b)
Normal kernel(c)
Epanechnikov kernel


## 4.2. Mean Shift Vector

It can be seen from Formula (3) that the sampling points falling into Sh make the same contribution to the computation of the final Mhx whether it is close or far away from x. However, we all know that generally speaking, the closer the sampling points are away from x, the more significant they are to estimate the statistical characteristics surrounding x. Therefore, we introduce the concept of kernel function and when computing Mhx, the impact of distance can be taken into consideration; in the meanwhile, we can also suppose that among all these sampling points xi, they are significant in different ways, so, we have introduced a weight coefficient for every sample.In this way, we can expand the basic Mean Shift form into(8)Mx≡∑i=1nGHxi−xwxixi−x∑i=1nGHxi−xwxi,in which Gx is a unit kernel function; H is a positive definite and symmetric d×d matrix, and we usually call it window width matrix; and wxi≥0 is a weight given to the sampling point xi, GHxi−x=H−1/2GH−1/2xi−x.In practical applications, the window width matrixH is generally restricted to a diagonal matrix H=diagh12,⋯,hd2 or even simply directly proportional to unit matrix, i.e., H=h2I. As the latter form only needs to confirm a coefficient h, Formula (8) can also be written as follows:
(9)Mhx≡∑i=1nGxi−x/hwxixi−x∑i=1nGxi−x/hwxi.We can see that if all sampling pointsxi satisfy the following conditions:
(1)
wxi=1(2)
Gx=1ifx<1,0ifx≥1Mean Shift vectorMhx is the normalized probability density gradient and iterative Mean Shift algorithm will converge to a stable centroid of probability density function [18].


## 4.3. Probability Density Gradient

For a probability density functionfx, it is known that there are n sampling points xii=1,⋯,n, in d-dimensional space, and then, the kernel function estimation (also called as Parzen windowing estimation) of fx is as follows:
(10)f^x=∑i=1nKxi−x/hwxihd∑i=1nwxi,in which wxi≥0 is a weight given to sampling point xi and Kx is a kernel function and it satisfies∫kxdx=1.Besides, the section function of the kernel functionKx is kx and it makes
(11)Kx=kx2.The negative derived function ofkx is gx, namely, gx=−k′x, and its corresponding kernel function is as follows:
(12)Gx=gx2.The estimation of gradient∇fx of probability density function fx is
(13)∇^fx=∇f^x=2∑i=1nx−xik′xi−x/h2wxihd+2∑i=1nwxi.According to the definition above,gx=−k′x and Gx=gx2. So, the formula above can be written as
(14)∇^fx=2∑i=1nxi−xGxi−x/h2wxihd+2∑i=1nwxi=2h2∑i=1nGxi−x/hwxihd∑i=1nwxi∑i=1nxi−xGxi−x/h2wxi∑i=1nGxi−x/hwxi.The part in the second square bracket in the right hand of the above formula is the Mean Shift vector as defined in Formula (9), and the part in the first square bracket is the estimation of probability density function fx with Gx as the kernel function, which is marked as f^Gx. Then, f^x as defined in Formula (10) is marked as f^Kx, so Formula (12) can be changed into
(15)∇^fx=∇f^Kx=2h2f^GxMhx.It can be seen from Formula (13) that
(16)Mhx=12h2∇f^Kxf^Gx.Formula (16) shows that the Mean Shift vector Mhx computed and obtained at point x with kernel function G is proportional to the normalized gradient of probability density function f^Kx estimated with kernel function K and the normalization factor is the probability density of point x estimated with kernel function G. Therefore, Mean Shift vector Mhx always points to the direction the probability density increases the most.The Mean Shift algorithm is an iterative step. In another word, it computes the Mean Shift of the current point. Then, this point is moved to this Mean Shift and it will become a new starting point. Continue to move until it satisfies the final conditions [19]. This process can be seen in Figure 2 below.Figure 2
Schematic diagram of the Mean Shift algorithm.
(a)(b)(c)(d)(e)(f)It can be seen from the above process that the Mean Shift is computed in the designated region. Move this point to the point of Mean Shift. Compute the new Mean Shift, and move it. Repeat this process until it meets the final conditions. Then, quit. In the Mean Shift algorithm, the most important key is to compute the Mean Shift of every point and then update the position according to the new Mean Shift.


## 4.4. Object Tracking Based on Mean Shift

The Mean Shift algorithm can initialize the object to be tracked by auto or semiauto methods. Semiauto is to manually designate the object region of interest in the initial frame while auto is to get the object region to be tracked through object detection method. Object region is the region where kernel function works, and its size is the window width (scale) of the kernel function. When the Mean Shift algorithm tracks the object, the object features usually choose color feature of the object. Real-time processing shall meet the requirement of low computation, and it can divide every subspace under certain color space intok equal regions, namely, k bins. The color histogram feature of the possible object region in the video image is the description of the candidate model. Generally, Epanechnikov function is chosen as the kernel function. Use the proper similarity function to compute the similarity of the candidate model and the object model, and use the maximum value of similarity function to get the Mean Shift vector, i.e., the shift of object in the current frame. The object will eventually converge to the real position after several iterations so as to achieve the purpose of tracking.


### 4.4.1. Description of Object Model

Assume thatxii=1,2,⋯,n represents the n pixels in the object region and the coordinate of the object center point is x0; then, the probability distribution density of all pixel points in this object region is qu.
(17)q^u=C∑i=1nkxis−x0h2δbxis−u,in which kx is the kernel function and it is used to represent the weight of object color histogram. The closer it is to x0, the bigger the weight. h is the window width of the kernel function, and bx is the color feature of the object region xi. δx is a 1D delta function, and it is used to judge whether the index value of xi is equal to the feature value u, and its value is 1 when they are equal and otherwise, 0. C is the normalization constant.
(18)C=1∑i=1nkxi−x0/h2.


### 4.4.2. Description of Candidate Model

The possible object region after the initial frame is the candidate region. Make its central position asy, and the pixels in the region are represented with xii=1,2,⋯,n. Compare the description of object model, and the probability density of the candidate model is as follows.The candidate object located iny can be described as
(19)p^uy=Ch∑i=1nhkxis−yh2δbxis−u,(20)Ch=1∑i=1nkxi−x0/h2.


### 4.4.3. Similarity Function

Similarity function is used to measure the difference or similarity between the object model and the candidate object model. In the Mean Shift algorithm, Bhattacharyya coefficient is the similarity coefficient and it refers to the approximate computation of the overlapping of two statistical samples and it is used to measure the correlation of two groups of samples [19]. Therefore, object tracking can be simplified into the search for the optimal y to make p^uy most approximate to q^u.The distribution of the similarity betweenp^uy and q^u is measured by Bhattacharyya coefficient ρ^y, namely,
(21)ρ^y≡ρpy,q=∑u=1mpuyq^u.Perform Taylor expansion at pointp^uy^0 on Formula (21), and obtain
(22)ρpy,q≈12∑u=1mpy0qu+12∑u=1mpuyqupuy0.Bring Formula (19) into the formula, and get
(23)ρpy,q≈12∑u=1mpy0qu+Ch2∑i=1nwiky−xih2,in which
(24)wi=∑u=1mδbxi−uqupuy0.


### 4.4.4. Object Localization

To search the real position of the object in the current frame, it is to find the largest candidate region. First, localize the object center in the previous frame as the object center of current frame and search the optimal matching region starting from this point. Make the center asy. Assume that various feature distribution densities of object candidate region are puyu=1,2,⋯,m and the coordinate of the central point of the object in the last frame is y0; then, the central position of the tracking object in the current frame is y1.
(25)y1=∑i=1mxiwigy0−xi/h2∑i=1mwigy0−xi/h2,in which gx=−k′x and wi is the weight.
(26)wi=∑u=1mqupuy0δbxi−u.Compute the value ofy1 through iteration. When the two neighboring iterative values are smaller than a certain threshold, the position in the current frame of the tracking object can be confirmed and the real position of the object can be found after several iterations.


## 4.4.1. Description of Object Model

Assume thatxii=1,2,⋯,n represents the n pixels in the object region and the coordinate of the object center point is x0; then, the probability distribution density of all pixel points in this object region is qu.
(17)q^u=C∑i=1nkxis−x0h2δbxis−u,in which kx is the kernel function and it is used to represent the weight of object color histogram. The closer it is to x0, the bigger the weight. h is the window width of the kernel function, and bx is the color feature of the object region xi. δx is a 1D delta function, and it is used to judge whether the index value of xi is equal to the feature value u, and its value is 1 when they are equal and otherwise, 0. C is the normalization constant.
(18)C=1∑i=1nkxi−x0/h2.


## 4.4.2. Description of Candidate Model

The possible object region after the initial frame is the candidate region. Make its central position asy, and the pixels in the region are represented with xii=1,2,⋯,n. Compare the description of object model, and the probability density of the candidate model is as follows.The candidate object located iny can be described as
(19)p^uy=Ch∑i=1nhkxis−yh2δbxis−u,(20)Ch=1∑i=1nkxi−x0/h2.


## 4.4.3. Similarity Function

Similarity function is used to measure the difference or similarity between the object model and the candidate object model. In the Mean Shift algorithm, Bhattacharyya coefficient is the similarity coefficient and it refers to the approximate computation of the overlapping of two statistical samples and it is used to measure the correlation of two groups of samples [19]. Therefore, object tracking can be simplified into the search for the optimal y to make p^uy most approximate to q^u.The distribution of the similarity betweenp^uy and q^u is measured by Bhattacharyya coefficient ρ^y, namely,
(21)ρ^y≡ρpy,q=∑u=1mpuyq^u.Perform Taylor expansion at pointp^uy^0 on Formula (21), and obtain
(22)ρpy,q≈12∑u=1mpy0qu+12∑u=1mpuyqupuy0.Bring Formula (19) into the formula, and get
(23)ρpy,q≈12∑u=1mpy0qu+Ch2∑i=1nwiky−xih2,in which
(24)wi=∑u=1mδbxi−uqupuy0.


## 4.4.4. Object Localization

To search the real position of the object in the current frame, it is to find the largest candidate region. First, localize the object center in the previous frame as the object center of current frame and search the optimal matching region starting from this point. Make the center asy. Assume that various feature distribution densities of object candidate region are puyu=1,2,⋯,m and the coordinate of the central point of the object in the last frame is y0; then, the central position of the tracking object in the current frame is y1.
(25)y1=∑i=1mxiwigy0−xi/h2∑i=1mwigy0−xi/h2,in which gx=−k′x and wi is the weight.
(26)wi=∑u=1mqupuy0δbxi−u.Compute the value ofy1 through iteration. When the two neighboring iterative values are smaller than a certain threshold, the position in the current frame of the tracking object can be confirmed and the real position of the object can be found after several iterations.


## 5. Application of Improved Mean Shift Algorithm in Object Tracking of Traffic Video Image

The Mean Shift algorithm is a nonparametric method of density function gradient estimation, and it localizes the object by obtaining the local maximum of density estimation function through iteration. The Mean Shift algorithm is fast in matching and needs no parameters so that it has been widely applied in the field of video object tracking. However, its object model is fixed, preventing the window width of kernel function from being updated timely and hurting the tracking accurately. If the size of motion object changes too significantly, the window width of fixed kernel function will lead to inaccurate object tracking or even lose the object tracking.To realize the practicability of object tracking, detailed analysis is made of the computation amount when applying the algorithm of this paper in object tracking. Real time has a high requirement in traffic video. Describe the motion object with grayscale and color space HS (hue and saturability). Assume that the center of the object is located inx0; then, the object is represented with the following formula:
(27)q^u=C∑i=1nkxis−x0h2δbxis−u.The candidate object located iny can be described as
(28)p^uy=Ch∑i=1nhkxis−yh2δbxis−u.Therefore, object tracking can be simplified into the search for the optimaly, making p^uy the most similar to q^u. The most similarity between p^uy and q^u is measured by Bhattacharyya coefficient ρ^y, namely,
(29)ρ^y=ρpy,q=∑u=1mpuyq^u.Perform Tylor expansion to Formula (29) at point p^uy^0, and obtain
(30)ρpy,q≈12∑u=1mpy0qu+12∑u=1mpuyqupuy0.Put Formula (28) into the above formula, and obtain
(31)ρpy,q≈12∑u=1mpy0qu+Ch2∑i=1nwiky−xih2,in which wi=∑u=1mδbxi−uqu/puy0 optimize Formula (29) and weight coefficient.The process of this algorithm is as follows: give an initial pointx, kernel function Gx, and allowable error ε. Through iterations, continuously move along the gradient direction of probability density until converging to the peak density in data space. The step length in iteration is not only related to the size of gradient but also related to the probability density of this point, and it is a gradient ascent algorithm with changeable step length.AssumeA is a finite set embedded in n-dimensional Euclidean space x. The Mean-Shift vector at x∈X is defined as
(32)ms=∑aka−xωaa∑aka−xωa−x,a∈A,in which k is kernel function and W is weight. The reverse direction of Mean-Shift vector ms computed at X points to the gradient direction of convolution surface:
(33)Jx=∑aga−xωa,in which g is shadow kernel. Move the central position of kernel function continuously along the direction of ms until convergence, and find the neighboring mode matching position.


### 5.1. Affine Model and Feature Point Matching

Here, only two types of common motion are considered: translation and scale. So, the affine model of the object is given by the following form:(34)x′y′=sx00syxy+exey,in which x,y′ and x′,y′ are the positions of the same object feature point in frames i and i+1, respectively. e=ex,ey is the translation parameter, and s=sx,sy is the scale amplitude in the horizontal and vertical directions of the object. By making use of s, the kernel window width can be updated by the following method:
(35)r=rmaxsx,sy.For rigid object, corner points can better depict its spatial structure and are easy to detect. Therefore, the matching corner points in the two frames are used as samples to estimate the parameters of the affine model.Assume that there areN and N′ corner points in the tracking windows Ti and Ti+1 of frames i and i+1, respectively. Ti and Ti+1 have the same radius, and both their centers coincide with the corresponding object centroids. In other words, the object centroid has already gone through registration in the adjacent two frames. Given a corner point PcTi located in Ti, its corresponding corner point PcTi in Ti+1 shall satisfy the following:
(36)IPcTi+1=minIPTi−IPjTi+1j=1,2,⋯,n,in which I is the grayscale of the pixel. n candidate points are located in a small given window G with the position of PcTi as the center in frame Ti+1.


### 5.2. Object Centroid Registration

Assume that in framei, the object with oi as the centroid is selected by the initial tracking window Ti with ci=oi as the center. When the object of increased size appears in frame i+1, for the current object centroid oi+1, there should be a deviation of d=ci+1−oi+1. Here, ci+1 is the center of the tracking window Ti+1 in frame i+1. This deviation is the deviation of spatial localization caused by the Mean Shift tracking algorithm of fixed kernel window width. As the size of the current object is larger than that of Ti+1, it only contains certain part of the object. At last, the position of the object centroid in frame i+1 is estimated as follows:
(37)oi+1≤ci+1−d′.Therefore, when an object image is given, Formula (37) can be used to register the object centroid in the current frame and then use Formula (36) to match corner point. This processing method can effectively remove mismatching points.


### 5.3. Algorithm Description

Step 1.
Get the initial tracking windowTi after selecting the object in frame i, and perform Mean Shift tracking in frame i+1 to obtain Ti+1.Step 2.
WithTi+1 as the initial tracking window, perform Mean Shift tracking in frame i and obtain Ti′.Step 3.
MoveTi+1 according to the position of central point between Ti and Ti′, and expand its size r=r·ε,ε>1.Step 4.
Extract the corner point for matching fromTi and Ti+1.Step 5.
Perform regression to the horizontal and vertical coordinates of matching point and getsx and sy.Step 6.
Update the size ofTi+1 with r=r⋅maxsx,sy.


## 5.1. Affine Model and Feature Point Matching

Here, only two types of common motion are considered: translation and scale. So, the affine model of the object is given by the following form:(34)x′y′=sx00syxy+exey,in which x,y′ and x′,y′ are the positions of the same object feature point in frames i and i+1, respectively. e=ex,ey is the translation parameter, and s=sx,sy is the scale amplitude in the horizontal and vertical directions of the object. By making use of s, the kernel window width can be updated by the following method:
(35)r=rmaxsx,sy.For rigid object, corner points can better depict its spatial structure and are easy to detect. Therefore, the matching corner points in the two frames are used as samples to estimate the parameters of the affine model.Assume that there areN and N′ corner points in the tracking windows Ti and Ti+1 of frames i and i+1, respectively. Ti and Ti+1 have the same radius, and both their centers coincide with the corresponding object centroids. In other words, the object centroid has already gone through registration in the adjacent two frames. Given a corner point PcTi located in Ti, its corresponding corner point PcTi in Ti+1 shall satisfy the following:
(36)IPcTi+1=minIPTi−IPjTi+1j=1,2,⋯,n,in which I is the grayscale of the pixel. n candidate points are located in a small given window G with the position of PcTi as the center in frame Ti+1.


## 5.2. Object Centroid Registration

Assume that in framei, the object with oi as the centroid is selected by the initial tracking window Ti with ci=oi as the center. When the object of increased size appears in frame i+1, for the current object centroid oi+1, there should be a deviation of d=ci+1−oi+1. Here, ci+1 is the center of the tracking window Ti+1 in frame i+1. This deviation is the deviation of spatial localization caused by the Mean Shift tracking algorithm of fixed kernel window width. As the size of the current object is larger than that of Ti+1, it only contains certain part of the object. At last, the position of the object centroid in frame i+1 is estimated as follows:
(37)oi+1≤ci+1−d′.Therefore, when an object image is given, Formula (37) can be used to register the object centroid in the current frame and then use Formula (36) to match corner point. This processing method can effectively remove mismatching points.


## 5.3. Algorithm Description

Step 1.
Get the initial tracking windowTi after selecting the object in frame i, and perform Mean Shift tracking in frame i+1 to obtain Ti+1.Step 2.
WithTi+1 as the initial tracking window, perform Mean Shift tracking in frame i and obtain Ti′.Step 3.
MoveTi+1 according to the position of central point between Ti and Ti′, and expand its size r=r·ε,ε>1.Step 4.
Extract the corner point for matching fromTi and Ti+1.Step 5.
Perform regression to the horizontal and vertical coordinates of matching point and getsx and sy.Step 6.
Update the size ofTi+1 with r=r⋅maxsx,sy.


## 6. Application of Mean Shift Algorithm in Remote Sensing Image Semantic Segmentation

The Mean Shift algorithm has also been successfully applied in many other fields, such as image smoothing and image segmentation, which belong to the part of pattern recognition or computer vision in artificial intelligence.In the postprocessing stage, a super pixel algorithm combined with traditional machine learning is proposed to further optimize the segmentation results [20].Although the deep convolution neural network has achieved good segmentation results in the semantic segmentation of remote sensing images, due to the inherent nature of the deep convolution neural network, its segmentation results often still have the following shortcomings:(1)
For high-resolution remote sensing images, due to the rich structure and texture of ground objects, the deep convolution neural network is not accurate for the semantic boundary segmentation of ground objects. This is due to the following reasons: in order to output the segmentation results consistent with the size of the original image, the deep convolution neural network generally uses upsampling or deconvolution to improve the size of the output feature image(2)
In remote sensing images, an object is often composed of a series of regions. In these areas, the color, illumination, and texture of the object change very little. Because the final segmentation result of deep semantic segmentation network is to classify each pixel, there is no relevant information that these regions belong to the same objectIn order to solve the above problems, we propose a region method based on Mean Shift algorithm superpixel segmentation for the postprocessing of deep convolution neural network semantic segmentation results, so as to improve the accuracy of remote sensing image semantic segmentation and the accuracy of boundary pixel classification.In the semantic segmentation network proposed in this paper, the segmentation performance of the network itself has reached a high level. In order to further improve the segmentation accuracy through postprocessing, an improved conditional random field based on traditional machine learning superpixel algorithm (SLIC) is proposed.Superpixel algorithm is an image oversegmentation method, which can aggregate the pixels in the image into irregular blocks according to their texture, color, brightness, and other characteristics. Each block can well reflect the boundary of the object.According to this characteristic, the oversegmentation template obtained by the superpixel algorithm is first applied to the network prediction results, and the categories of all pixels in each over segmented block are unified into the classes with the largest number. Then, the optimized prediction results and the input RGB image are sent to the condition ci in Figure3.Figure 3
The architecture of our proposed method combining DCNN and superpixel segmentation.The detailed Algorithm1 flow is as follows.Algorithm 1
(1) The image to be segmented input to the network is defined asI, and the prediction image result of the network is defined as O.All object classes of the dataset are defined asC=c1,c2,⋯⋯,ck.(2) Calculate the superresolution algorithm of imageI, and generate superpixel blocks with Mean Shift method, which are defined asS=s1,s2,⋯⋯,sk. sj is one of the super-pixel block.(3) Fori=1:MAllN pixels in Si are defined as T=ti1,ti2,⋯⋯,tk∈ get the prediction result IijIij∈C of each pixel of pij.Count the number of pixels of each classes insi, and the result is countc1,countc2,⋯⋯,countcj®(4) Change the prediction classes of each pixelpij in si toZsi=maxcountc1,countc2,⋯⋯,countcjEnd for(5) Update the output image toZ.(6) Calculate the input image and the updated prediction result imageZ to obtain the final prediction result Lout.


## 7. Experiment Result and Analysis

Turn the video sequence image with vibrations into stable video sequence image. After the object affine model is obtained through regressive calculation, the current kernel window width is updated. The updated kernel window width is used to, on the one hand, correct the size of the current tracking window so as to reduce the deviations of scale localization and, on the other hand, determine the number of samples in Mean Shift iteration in tracking the next frame. In this way, the system can better get adjusted to the change of object scale and overcome the restrictions of fixed kernel window width. Experiment 1 is the tracking experiments on bumpy motion object in traffic video through the algorithm of this paper and the Mean Shift tracking algorithm.Experiment 1.
Use the video with a frame rate of 30 frames/second and a resolution of256∗256 where the vehicle goes on bumpy road. The tracking effect of the Mean Shift algorithm is shown in Figure 4 while that of the algorithm in this paper is shown in Figure 5.Figure 4
Tracking effect of bumpy vehicle via the Mean Shift algorithm.
(a)
3rdframe(b)
16th frame(c)
42nd frame(d)
66th frameFigure 5
Tracking effect of bumpy vehicle via the algorithm of this paper.
(a)
3nd frame(b)
16th frame(c)
42nd frame(d)
66th frameBy comparing the motion object tracking effects by the algorithm of this paper and the Mean Shift algorithm, it is clearly evident that both algorithms can perform accurate tracking on the object the size of which cannot change dramatically. But as the algorithm of this paper can automatically adjust the kernel function window width, it can frame the object more accurately, namely, that such features as the color of the object obtained are more accurate, and it improves the tracking robustness. As a nonparametric density estimation method, it is clear that the tracking algorithm of this paper has better accuracy and stability on object tracking. Besides, it does not need much computation and it can satisfy the real-time requirement.Figure4 indicates the effects of motion object tracking of the 3rd, 16th, 42nd, and 66th frames in the video using the Mean Shift algorithm, and the red circles have marked the final object position determined by this algorithm. We can see that although the tracking box can always track the object, the effect is not ideal; it may lose the object if the object becomes increasingly big.Figure5 shows the effects of motion object tracking of the 3rd, 16th, 42nd, and 66th frames in the video using the algorithm of this paper, and the red circles have marked the final object position determined by the algorithm of this paper. Compared with the Mean Shift algorithm, it can be seen that the algorithm mentioned in this paper can perform complete tracking of the entire motion object and it can also better extract the feature information of the motion object and effectively prevent the loss of object.Experiment 2.
The video is a real video of a car driving. The frame rate of the video is 30 frames per second, and the resolution is1280∗720. The car is the object we need to track, and the scale of the object is getting larger. Intercepted 5th, 47th, 76th, and 119th frames were intercepted for analysis. Figure 6 is the experimental result of the Mean Shift algorithm, and Figure 7 is the experimental result of our algorithm.Figure 6
Tracking effect of vehicle from far to near by the Mean Shift algorithm.
(a)
5th frame(b)
47th frame(c)
76th frame(d)
119th frameFigure 7
Tracking effect of vehicle from far to near by our algorithm.
(a)
5th frame(b)
47th frame(c)
76th frame(d)
119th frameAs shown in Figure6, we can see that the traditional Mean Shift algorithm gradually loses most of the pixels of the tracking object when the object becomes larger. Although the window becomes larger with the increase of the object, there are serious deviations in the location of the object center. Figure 7 adopts the algorithm in this paper. The object scale can be adjusted adaptively. It can not only update the object scale accurately but also locate the center of the object accurately. Besides, Figure 8 shows the comparison curves about the size of object tracking box (unit: pixel) and the real size of the object through the algorithm of this paper and the Mean Shift algorithm.Figure 8
Analysis diagram of the algorithm in this paper and Mean Shift tracking window size.In Figure8, the blue “♦” line represents the actual scale of the object, the green “▲” line represents the Mean Shift algorithm, and the red “■” line represents the algorithm in this paper. It can be clearly seen from the graph that the object scale of the Mean Shift algorithm is increasing, but it is far away from the actual object scale, and the algorithm in this paper is very close to the actual object scale. Table 1 is the statistics of relative error of size of some frame object tracking boxes in the video sequences and after analysis.Table 1
Error comparison between the algorithm of this paper and Mean Shift tracking box.
Real size/pixel of objectSize/pixel of this algorithm tracking boxSize/pixel of mean shift tracking boxThis algorithm relative error (%)Mean shift relative error (%)1st frame5676166198.64%9.17%5th frame6096508966.73%47.13%47th frame2280247227548.42%20.79%76th frame56266258673211.23%19.66%119th frame1815819573201987.79%11.23%131st frame1963621289228158.41%16.19%It can be observed from above experimental results that the tracking algorithm in this paper will have deviation in spatial localization when the size of object keeps growing and it is bigger than the kernel window width. After this deviated position is obtained, back processing can be conducted, namely, backtracking. At this time, reverse video sequence is equivalent to gradual shrinkage in object size. In this way, it can accurately identify the corresponding deviated point in the reverse frame, making compensation for this deviation possible. So, the change of translation and scaling is obtained for the position of window, making the object window adaptively change over the changing object size. Based on the assumption that the rigid motion object in consecutive frames meets the affine model, firstly, register the object centroid in compensation for deviation in spatial localization with a back tracking method. On the basis of registration, the feature point coordinates in the tracking window of neighboring frames are normalized into the coordinate system with the object centroid as the origin. In this way, compared with the matching feature points of two unregistered tracking windows, the method of this paper can effectively reduce mismatching so as to lay a solid foundation for accurate estimation of scaling amplitude in the affine model of object; the kernel window width is updated according to scaling amplitude and verification from different perspectives. The algorithm mentioned in this paper is obviously better than the Mean Shift algorithm after being verified from different perspectives [21–25].To evaluate the performance of different methods for semantic segmentation of aerial images,F1 score and overall accuracy are used as evaluation criteria. The overall accuracy (OA) is defined in Equation (14). The OA is the ratio of the number of correctly classified pixels to the total number of pixels.
(38)OA=TP+TNP+N,where TP+TN represents the number of correctly classified pixels and P+N represents the total number of pixels.The accuracy of each category is evaluated using theF1 score.
(39)Precision=TPTP+FP,Recall=TPTP+FN,F1=2xprecision×recallprecision+recall, where TP, FP, and FN are the numbers of true positives, false positives, and false negatives, respectively.To verify the effectiveness of the proposed method, we perform comparisons against two state-of-the-art semantic segmentation networks, i.e., SegNet [26] and DeepLabv3+ [27], which are two most widely used models in semantic segmentation of aerial images.The setting is the same as the cited paper [27].Table 2 presents results on the ISPRS Vaihingen dataset, and we can see that the proposed algorithm significantly outperforms other methods on both F1 score and overall accuracy. Compared to DeepLabv3+, the proposed method (DeepLabv3+∗) increases the mean F1 score and overall accuracy by 0.3 and 0.19%, respectively; in comparison with SegNet, increments on mean F1 score and overall accuracy are 0.27% and 0.12%, respectively.Table 2
Comparison results on Vaihingen dataset ∉.
VaihingenOA (%)PrecisionRecallMeanF1FCN88.1184.5685.9185.68SegNet90.0788.9388.8388.62BiseNet90.1388.7988.8988.71DeepLabv3+90.0688.9588.9788.67FCN+∗88.3384.7986.0285.86SegNet +∗90.1988.9288.8688.89BiseNet+∗90.2188.9388.9788.67DeepLabv3+∗90.2588.9488.9988.97DeepLabv3+∗ stands for DeepLabv3 + and superpixel segmentation method based on Mean Shift.On the ISPRS Vaihingen dataset, the first line is the original image, the second line is the result of DeepLabv3puls, the third line is the combination of DeepLabv3plus and Mean Shift superpixel segmentation, and the last line is the BiSeNet with shift superpixel method.As can be seen from Figure9, the segmentation method of DeeplabV3+ and Mean-Shift fusion proposed in this paper realizes the separation of different plots, and the boundary line of the divided area is well matched with the boundary line of the real objects, while maintaining the integrity of the plot. In summary, the results of the DeeplabV3+ and Mean Shift based on superpixel segmentation methods proposed in this paper are significantly better than the current best-performing DeepLabv3+ methods.Figure 9
Example results on the Vaihingen dataset.


## 8. Conclusion

Object tracking contains not only motion information of the object in the image but also rich information of 3D physical structure; therefore, it can be used to pin down the object motion and reflect other image information. Traffic video object tracking is an important method to analyze motion sequence image. Objected at the flaws of Mean Shift object tracking algorithm in complex road conditions, this paper has proposed an improved Mean Shift object tracking algorithm. Apart from such strengths as adaptive size of tracking framework and high real time, this algorithm can also adaptively adjust the stability of video image, remove background interference similar to object colors, and effectively track the object. The experiment has proved that the algorithm in this paper is effective. In addition, a model that combines the Mean Shift algorithm and deep convolutional neural network is proposed, which is beneficial to improve the semantic segmentation of aerial images. The experimental results show that our method can achieve higher segmentation accuracy with less running time compared with the existing advanced methods and fully proves its superiority.



---

*Source: 7205929-2022-05-16.xml*