Ann. Telecommun. DOI 10.1007/s12243-017-0572-9

An improved tracking algorithm of floc based on compressed sensing and particle filter Xin Xie1 · Huiping Li2 · Fengping Hu4 · Mingye Xie3 · Nan Jiang1 · Huandong Xiong1

Received: 30 August 2016 / Accepted: 28 February 2017 © Institut Mines-T´el´ecom and Springer-Verlag France 2017

Abstract In order to solve the problem of tracking flocs during complex flocculating process, we propose an improved algorithm combining particle filter (PF) with compressed sensing (CS). The feature of flocs image is extracted via CS theory, which is used to detect the singleframe image and get the detection value. Simultaneously, the optimal estimation of particle in the space model of non-linear and non-Gaussian state is obtained by PF. Then, we correlate the optimal estimate with the detected value to determine the trajectory of each particle and to achieve

flock tracking. Experimental results demonstrate that this improved algorithm realizes the real-time tracking of flocs and calculation of sedimentation velocity. In addition, it eliminates the shortcomings of heavy computation and low efficiency in the process of extracting image features , and thus guarantees the accuracy and efficiency of tracking flocs. Keywords Compressed sensing · Particle filter · Flocs tracking · Sedimentation velocity

1 Introduction  Xin Xie

[email protected] Huiping Li [email protected] Fengping Hu [email protected] Mingye Xie [email protected] Nan Jiang [email protected] Huandong Xiong [email protected] 1

School of Information Engineering, East China Jiaotong University, Nanchang, People’s Republic of China

2

Team of Intelligence Information, Xiangtan City Public Security Bureau, Hunan, People’s Republic of China

3

School of Information Science Technology, East China Normal University, Shanghai, People’s Republic of China

4

School of Civil Engineering, East China Jiaotong University, Nanchang, People’s Republic of China

Floc sedimentation velocity detection (FVD) is an efficient and accurate detection method,which is based on image processing technology. It takes the sedimentation velocity of floc as the main parameter, and avoids the influence of physical and chemical factors effectively. FVD, as an important part, can understand the coagulation state in real-time and collect target parameters for trajectory tracing of floc and sedimentation velocity measurement. FVD provides a basis for judging the dosage of coagulant. Floc tracking is a prerequisite for the floc sedimentation velocity measurement. Scholars have proposed various algorithms of flocs tracking [1–4]. Reference [1] proposed an improved multiple hypothesis tracking (MHT) algorithm combined with the cost function for floc tracking. The algorithm solves the issues of trajectory intersection etc. but there exists a problem of failing to predict the floc location of next moment effectively. Reference [2] combined the adaptive Kalman filter algorithm with fuzzy inference association algorithm, which can solve the problem of flocs overlap merging in tracking process effectively. However, it brings large amount of calculation, which restricts the

Ann. Telecommun.

algorithm application in industry. Reference [3] pointed out that when the adaptive Kalman filter algorithm was combined with data association algorithms, it had moderate computational complexity and solves the occlusion problem effectively. But, it has low accuracy. The above methods can complete flocs tracking in some particular states, but their accuracy is not high. So, it is necessary to improve further folcs tracking in complex environment In 2003, Cartis C put forward a multiple flocs tracking algorithm based on particle filter [5], which obtains the optimal state solution set by using a set of weighted particles to approximate probability hypothesis density. Because of the deficiency of data correlation, it cannot establish one-on-one flocs trajectory. In 2008, Zhang Yan put forward a particle filter multi floc tracking algorithm based on dynamic significant feature [6]. This algorithm used visual saliency map for single frame motion detection, and correlated the predicted floc position to the floc location. According to the result of correlation, it can manage track of each moving flocs. Therefore, this algorithm can achieve the one-to-one flocs trajectory. However, it is difficult for industrial implementation. Because the acquisition of visual saliency map is complex for large computation, and the image quality requirement is relatively high. Li [7] presented an improved particle filter (PF) algorithm based on the generalized likelihood (GL) weighting method. For the sake of reducing computational burden, he presented another group tracking algorithm based on box particle filter (Box-PF). Firstly, the rectangular box particles are sampled in the target state space. Then, the ratio of the contracted to the predicted box particle volumes is used to calculate the weighting of particles by the interval analysis and constraint propagation method. Lastly, the group structure is estimated based on the estimation results of group target state and the evolving network model. The Box-PF algorithm can achieve greater computational efficiency and reduce the peak error of the estimation results. In order to reduce the influence of complex environment like illumination variation, Zhou [8] proposed a hybrid particle filter tracking method based on global and local information. The local binary patterns (LBP) textual feature was introduced into the particle filter algorithm. Through sparse coding target sub-block, the local information was fully utilized, and the global information was taken into account to determine the position of target in the current frame. During the tracking, the robustness of the tracking algorithm was improved since the template was updated in real time. Experimental results showed that the proposed tracking algorithm achieved good results in complex background. Wang [9] also put forward some useful methods. A particle filtering algorithm based on compressive sensing was proposed in reference [10]. The extracted features were added into the framework of particle filtering tracking

by compressive sensing of the improved compressive tracking (CT) algorithm. The credibility of extracted features, including the color features of original particle filtering and compressive sensing features, was judged to deal with the target occlusion effects and illumination changes. Experimental results showed that the proposed algorithm brought better robustness and the accuracy of tracking targets in real time. In order to solve the problems of object occlusion and illumination change in the process of target tracking, Yang [11] proposed a target tracking algorithm based on particle filter and compressive sensing. The color feature and texture feature were fused to describe the object to improve the robustness of the algorithm in the illumination change and complex environment. The theory of compressive sensing was used to reduce the dimension of the feature, and improve the real-time performance of the algorithm. Therefore, the target condition was estimated according to the principle of particle filter, and then the target position could be obtained. In 2015, considering the shortcomings of massive calculation and slow speed of traditional scale invariant feature transform (SIFT) algorithm, Xie Xin and others proposed an improved image mosaic method, which combined wavelet transform (WT) and compressed sensing algorithm [12]. Firstly, images were transformed with wavelet and compressed using compressed sensing technology. Then, the image feature points were extracted and combined with SIFT algorithm. Finally, sequential similarity detection algorithm (SSDA) with adaptive threshold was used for fast search of image matching to find out an optimal stitching line, and obtained a panoramic image. Experimental results demonstrated that the method realized fast image matching, overcomed the shortcomings of heavy computation and low efficiency in extracting image features, and guaranteed matching accuracy and stitching efficiency. These met the real-time requirements in machine vision system. This algorithm could be applied to image matching and stitching in the field of digital image security. However, because of the different sizes of images, the problem of choosing initial template’s position and size needed further research in SSDA with adaptive threshold algorithm. In order to solve these problems, they proposed a new improved image matching method, which combined SIFT with SSDA based on compressed sensing [13]. However, it is not stable for the color images, thus in this respect the algorithm needs further research. Compressed sensing is a kind of technology that uses compressible signal to achieve signal reconstruction when acquires signal. It compresses the data appropriately reduces the sampling data, and saves storage space at the same time. However, it still contains a sufficient amount of information, thus it can use signal compression value as its characteristic value [14, 15]. In video monitoring, the compressed sensing technology can be carried out for the video compression

Ann. Telecommun.

effectively. It is advantageous to storage, and there is almost no distortion after extracting the information, ensuring the requirement of the small storage space and high accuracy [16]. The compressed sensing technology means compressing two images in image contrast, using compression value as image characteristic values, and it judges whether two image is the same image by contrasting image compression value [17]. The technology can reduce a large number of workload and improve the accuracy of contrast. In floc detection, it uses the compressed sensing technology to obtain flocs images’ compression value as the characteristic values, and detects single frame image of moving floc to obtain the detected value,and in the same time utilizes particle filter to forecast flocs’ position. Then, data association is performed between detect values and predict values. In the end, it achieves floc track management and the one-to-one flocs trajectory for every moving floc according to the result of correlation. Because image feature is obtained by the compressed sensing technology, the floc detection has the characteristics of high efficiency and high precision. And it is good for industrial implementation. In video enhancement system, firstly, it gets image compression value by the compressed sensing technology. Secondly, it finds the image points which needs enhancing by analysis of the compression value. Finally, it realizes targeted enhancement for image. This greatly reduces the time to find out the point. What is more, it is fairly targeted.

2 Use compressed sensing to extract image features Reference [4] states that if the signal X ∈ R N is compressible on an orthogonal basis or tight frame  , the transform coefficient  =  T X could be obtained. And  is equivalent or approximate sparse representation of . A smooth observation matrix  with M * N dimensions, which is irrelevant with transform base , is designed. We observe the  to get the observation set Y =  or Y =  T . The process can also be expressed as a non-adaptive observation of the signal X through the matrix ACS : Y = ACS X (ACS =  T ), and the ACS is called CS information operator. Since Y contains the unique information of the signal, the Y value of each different signal is different. For the case where the signal is an image, the compressed data Y may be represented as a feature of the image. The reference [17] proposed compressive tracking algorithm, and its formula is as follows: V = PX

signal is transformed into a one-dimension for the floc candidate region, where P is the feature extraction matrix and V is characterized. For this algorithm, the output in Eq. 1 is very important, and the different output produces different characteristics. In the reference [18], matrix P is defined as follows:

P ij

⎧ ⎨ 1 √ = s× 0 ⎩ −1

probability is 1/2s probability is 1−1/s probability is 1/2s

(2)

Therefore, the use of compression sensing technology can quickly and accurately extract the image features.

3 The basic theory of particle filter Over the last few years, particle filter, which is also known as condensation or sequential Monte Carlo, has proved to be powerful tools for image tracking [18, 19]. The particle filter algorithm which is represented by particle probability density, is a sequential Monte Carlo simulation method based on the Bayes principle. It is applied to the online state estimation. In the state space, the random sampling (particle) is used to represent the posterior probability density, and the posterior probability density is updated with the new observations. Particles distribute, reproduce, and weigh recursively according to the Bayes principle to get a recursive description of the posterior probability density. An assumed system model is as follows: Xk+1 = f (Xk ) + Wk+1

(3)

Zk = g(Xk ) + Vk

(4)

f (·) and g(·) are non-linear functions. Wk+1 and Vk are unrelated zero mean process noise and measurement noise. Their covariance is Qk and Rk , respectively. {Xk } is the state vector sequence of system and {Zk } is the observations of the system state vector {Xk }. The purpose of filtering is to estimate the posterior probability distribution according to the observation data, especially the border posterior probability distribution p(Xk |Zk ). Thus, we can obtain the optimal estimate of the system state. According to the empirical distribution, the posterior probability distribution p(X0,k | Zk ) can be approximately expressed as:

(1)

Where X ∈ R n×1 is the original signal, P ∈ R k×n (k << n) is the measurement matrix, and V ∈ R k×1 is the compressed data. For the floc image of the study, the

p(X0,k |Zk ) ≈

N  i=1

i wki δ(X0,k − X0,k )

(5)

Ann. Telecommun.

Boundary posterior probability distribution can be approximately expressed as: p(Xk |Zk ) ≈

N 

wki δ(Xk − Xki )

(6)

i=1

Where Xki is the ith particle randomly selected from the importance distribution q(Xk |Zk ) on time K. Then, δ() is Dirac function, and wki is the normalized importance weights of particles. Moreover, the selecting criteria of important distribution is minimum variance. When particle filter is used as a state estimator, it is not limited by non-gaussian and nonlinear, and it has high precision [20]. Particle filter gets rid of the situation that the random quantity must satisfy the restriction of the Gaussian distribution in nonlinear and non-Gaussian filtering problem, which can utilize more non-linear tracking information. In floc tracking, we are able to use the observed linear, non-linear information, greatly improving tracking efficiency. In addition, the particle filter as a state estimator which is not restricted by gauss linear, has high accuracy.

4 The improved flocs tracking algorithm This improved algorithm associate detection position of flocs and estimated location of flocs obtained by particle filter with data. Then, according to the associated effect, we can manage each flocs track and update each track of flocs constantly. The process of floc tracking algorithm is shown in Fig. 1. Compressive sensing technology is utilized to extract characteristics of flocs. Compared with the single method, it is more efficient and strong anti-interference in the case of extracting the image features. Firstly, extracted characteristics are used to detect the single movement frame image. Secondly, we obtain the initial path information and the detection position of floc with the principle of particle filter. Thirdly, initial path information and the characteristics are used to initial the filter and the feature is combined with the filter. Then, combine result will be set as the state characteristic of filter. Fourthly, floc tracking will be carried on to obtain flocs estimate position. Finally, if make the test location data associated with the estimated position and get trajectory of each floc, we could achieve one-one-one track management. The steps of improved algorithm are as follows: (1) Using compressive sensing to get image features The flocs image will be obtained from the computer control system in a certain cycle continuously. Then, we put it into the computer for subsequent processing through the image acquisition card. After that, compressive sensing

Fig. 1 The process of floc tracking algorithm

technology is used to compress the image and we can get the image characteristics Vt , and the value of t is set as 1, initially. As follow, these characteristics will be taken as the state vector of particle filter to initial the particle swarm. We set a function whose probability density distribution is known by us, as the prior distribution q. Then, we take sample according to the probability and obtain the initial particle swarm which is called Vit,n . In this case, n is the number of

Ann. Telecommun.

particle swarm which is change with the number of flocs, i is the number of particles in each of the particle swarm, and t is the moment (n = 1, 2, · · · , N , i = 1, 2, · · · , I ). According to the formula (6), the expression of the weights of particle importance is as follows:

i )= w(Vt,n

i )p(V i ) p(Zt, n|Vt,n t i |Z ) q(Vt,n t,n

(7)

n = 1, 2, · · · , N; i = 1, 2, · · · , I . At the same time, based on the initial image information, the initial path information is generated, which is Nt (n), t = 1, n = 1, 2, · · · , N . N is the total number of paths. (2) Importance sampling According to the q function (the ith particle of the nth i . particle swarm in the tth image), we can sample the Vt,n i Then, important weights wt,n could be estimated via formula (7) and the observation value Zt,n of time t. After that, we should normalize the weights. That is:

wt,i n

  i p Zt, n |Vt,i n )p(Vt,i n |Vt−1, n i   = wt−1, n i q Vt,i n |Vt−1, , Z t, n n

(8)

n = 1, 2, · · · , N; i = 1, 2, · · · , I . Then, optimal estimate of the floc could be gotten by the formula (8):

Vt,n = E{Vt,n | Z1:t,n } =

I 

i i wt,n Vt,n

(9)

5 Algorithm simulation and results analysis For the purpose of verifying the feasibility of the algorithm, we use Matlab, Visual C++, and GSL library to achieve mixed programming. In simulation 1, we set an experimental base, which includes a few of pools. For flocculation, precipitation, and other crafts, the base is used to simulate the complex flocculating process. And then, the algorithm which is proposed in this paper is used to track three moving flocs and observe the precision of the improved algorithm. In simulation 2, the improved algorithm is applied to track the actual flocs. The purpose of simulation 2 is to exam the effectiveness of the improved method about the sinking speed. (1) Simulation 1, three moving flocs are produced according to certain rules (the x-direction velocity is 1.2 m/s, y-direction velocity is 0.5 m/s). Then, we compare the method in this paper with the significant characteristic method to find out the difference between the two tracking effect. The experimental simulation results are shown in Figs. 2 and 3 (N = 5000, Nthres = 500). The blue, red, and green lines are used to represent the tracking of the three samples, respectively. From the compared results of the two methods, it can be seen that the tracking trajectory of improved algorithm is more closer to actual trajectory of the floc. Also, the result of improved algorithm has high precision and it will not cause the loss of floc. After that, the time consuming of improved algorithm is less than the other one. At last, the tracking effect is more obvious when the number of flocs increases. (2) Simulation 2, we use the experimental base and put a sensor at the bottom of the flocculation tank firstly. When the water through the sampling window smoothly and slowly, we use the industrial camera to obtain the water

i=1

n = 1, 2, · · · , N; i = 1, 2, · · · , I . (3) Data correlation By performing single frame image detection on the feature map corresponding to each scene image [6], the detection position of the floc is obtained. The optimal estimate of the filter is correlated with the position obtained by detecting the floc, and then we modify the floc track according the associated results. (4) Resampling According to the weight of each particle, the high weight particles are copied and the low weight particles are discarded, and I * N new particles are obtained. This can effectively reduce the probability of occurrence of particle degradation problem. Then, the execution point return to step (2) and the whole process is circulating in this way.

Fig. 2 The effect of significant method

Ann. Telecommun.

Fig. 5 Figure of flocs’ state Fig. 3 The effect of the method in the paper

(floc) images from sampling window continuously. In this process, we set the sampling interval according to the actual demand. In this experiment, the time interval is set as 1 s and the particle number is around 100, because the flocs in the sampling window have better representative. After that, this experiment condition can be used as samples of analysis of sinking speed. In one of the results, particles of each frame image are divided into three small samples according to the area of each particle. By calculating the average speed of three small samples, the flocs sinking speed monitoring diagram which is shown in Fig. 4 could be obtained. In Fig. 4, three curves represent average speed of the three small samples. Another experiment results record one of the frame in settlement of the floc and the trajectories of the three flocs are marked. As shown in Fig. 5, the curve is the track.

Figures 4 and 5 show the results of simulation 2. And the design of simulation 2 is used to get more precise data. In order to get more accurate data, we set an experimental environment to simulate the process of tap water and use a better experimental method to obtain it. As it is shown in the experiment, the sinking speed of flocs is mostly concentrate in the range 0.18 ∼ 0.24 mm/s. According to relevant data, the speeds obtained by the method in this paper are in normal range and the described trajectory is consistent with observation. We use this two simulations to prove that the proposed approach is better than existing approaches. The first simulation has two contrast experiment. As it is shown in the experiment, the tracking trajectory using the improved algorithm is closer to actual trajectory of the floc. Also, it has high precision. In the second simulation, we get results from two kinds of situations. So we quite certain that the experiment is effective.

6 Conclusion and prospect

Fig. 4 The figure of floc sinking speed monitoring

In this paper,an improved flocs tracking algorithm is proposed, which combines compressed sensing technology with the particle filter. Our algorithm can establish the trajectory of every floc, and improve tracking efficiency and accuracy. Compared with attention detection method by simulation, experimental results show that our algorithm obtains satisfactory results for floc tracking and sedimentation velocity measurement. It can conduct floc tracking continuously and monitor floc sedimentation velocity accurately in a real time, which can provide reliable data support for the subsequent operations [15, 16]. Because the proposed method can guarantee the accuracy and efficiency

Ann. Telecommun.

when it is used to extract features, as an extension, it can be applied to facial feature extraction and vehicle feature extraction. It also overcomes shortcomings of heavy computation and low efficiency for extracting image features, therefore the method can extract small characteristics of the face or car, and then apply to information security. But the sample impoverishment problem of the particles will affect the tracking effect of the algorithm, the solution need to further study. At the same time how to apply compressed sensing to the video technology should be the subject of in-depth study in the future. Acknowledgments This work is supported by the National Natural Science Foundation, under Grant nos. 61640217, 41402290, 61462028, Science and Technology Support Program of Jiangxi Province, under Grant no. 20151BBE50055, and Landing Plan of Scientific and Technological Project of Jiangxi Provincial Colleges and Universities, under Grant no. KJLD2013037, Cultivation Plan of Leadership for Excellence Jiangxi Province and Poyang Lake 555 Engineering, under Grant no. S2013-57, and Science and Technology Project supported by education department of Jiangxi Province under Grant no. GJJ150541, and Nanchang City Sensor Network and Compressed Sensing Knowledge Innovation Team under Grant no. Hong Sci(2016)114.

6.

7. 8.

9.

10. 11.

12.

13.

14. 15.

References 1. Zhong DH, Xia CY, Song QM, Mao WL (2008) Research and application on multi-target tracking algorithm. Comput Meas Control 16(6):846–849 2. Song ZY, Song QM, Yi-Ran BA, Peng F (2010) Surf: research on the method of online measuring oc settling velocity. Autom Instrum 25(5):4–7 3. Song XF (2006) The research of water floc online detection system. Shanghai University, Shang Hai, pp 39–49 4. Metzler CA, Maleki A, Baraniuk RG (2016) From denoising to compressed sensing. IEEE Trans Inf Theory 62(9):5117–5144 5. Cartis C, Thompson A (2013) A new and improved quantitative recovery analysis for iterative hard thresholding algorithms

16.

17.

18. 19.

20.

in compressed sensing. IEEE Trans Inf Theory 61(4):2019– 2042 Zhang Y, Zhang ZL, Shen ZK, Lu XY (2008) The images tracking algorithm using particle filter based on dynamic salient features of targets. Acta Electron Sin 36(12):2306–2267 Li ZX, Liu JM, Li S, Bai DY, Ni P (2015) Group targets tracking algorithm based on box particle filter. Acta Autom Sin 41(4):785–798 Zhou ZP, Zhou MZ, Li WH (2016) Object tracking algorithm based on hybrid particle filter and sparse representation. PR AI 29(1):22–30 Wang YX, Zhao QJ, Cai YM, Wang B (2016) Tracking by autoreconstructing particle filter trackers. Chin J Comput 39(7):1294– 1306 Wu XY, Wu LL, Yang L (2015) Particle filtering tracking based on compressive sensing. Syst Eng Electron 37(11):2617–2622 Yang FR, Liu T, Liu XF (2016) Target tracking algorithm based on particle filter and compressive sensing. Appl Electron Tech 42(7):130–133 Xie X, Xu Y, Liu Q, Hu FP, Cai TJ, Jiang N (2015) A study on fast sift image mosaic algorithm based on compressed sensing and wavelet transform. J Ambient Intell Humanized Comput 6(6):835–843 Xie X, Xu Y, Hu FP (2015) Image matching algorithm combining SIFT with SSDA based on compressed sensing. J Inf Comput Sci 12(16):6145–6153 Zhang JL, Zhang HQ, Dai RY (2016) Fast image matching algorithm based on MIC-SURF. Comput Eng 42:210–214 Jiang N, You H, Jiang F, He YS (2014) DCSH: distributed compressed sensing algorithm for hierarchical wireless sensor networks. Int J Comput Commun Control 9(4):425–433 Yang Y, Liu F, Xu W, Crozier S (2014) Compressed sensing MRI via two-stage reconstruction. IEEE Trans Bio-Med Eng 62(1):110–118 Ren YM, Zhang YN, Li Y (2014) Advances and perspective on compressed sensing and application on image processing. Acta Electron Sin 40(8):1563–1575 Zhang KH, Zhang L, Yang MH (2012) Real-time compressive tracking. Eur Conf Comput Vis 7574:864–877 Xie X, Li HP, Hu FP, Li B (2013) An improved tracking algorithm of floc based on particle filter. Int J Digit Content Technol Applic 7(8):84–91 Yu L, Wei C, Jia J, Sun H (2016) Compressive sensing for cluster structured sparse signals: variational Bayes approach. Let Signal Process 10(7):770–779