CN106803265A - Multi-object tracking method based on optical flow method and Kalman filtering - Google Patents

Abstract

The invention discloses a multi-target tracking method based on an optical flow method and a Kalman filter. First, an input video frame is processed through the optical flow method. Secondly, outliers are removed by optical flow clustering. Then, through morphological expansion and improved median filtering, the accurate acquisition of moving targets can be realized. Finally, according to the obtained target information, the Kalman filter method is used to process the subsequent image sequence and predict the moving target, so as to realize the effective tracking of the moving target. The invention does not need to train classifiers and construct target templates, and can better mark moving targets with optical flow information after clustering processing.

Description

Multi-target Tracking Method Based on Optical Flow and Kalman Filter

technical field

The invention relates to a target tracking algorithm, in particular to a multi-target tracking method based on an optical flow method and a Kalman filter, and belongs to the field of computer vision.

Background technique

Vision is one of the main means for humans to obtain information from the natural environment. Under the irradiation of visible light, the surrounding environment forms an image on the retina of the human eye, which is converted into nerve impulse signals by photoreceptor cells and transmitted to the cerebral cortex through nerve fibers for processing. and analysis. Computer vision is a computer simulation of the visual function of the human eye, extracting effective information from images, and analyzing the morphology and kinematics of the background and targets in the environment. Target tracking based on image processing technology is one of the frontier topics in the field of computer vision, and its research involves image analysis, computer vision, pattern recognition, machine learning, automatic control and other fields. At the same time, target tracking has a very broad application prospect, mainly involving intelligent video surveillance, intelligent vehicle assisted driving, visual navigation, virtual reality, weapon guidance and so on. Therefore, the research on target tracking has very important theoretical and practical significance.

With the popularization of computers and various multimedia devices, it is convenient for researchers to use various image acquisition devices to obtain external environmental information and convert them into digital signals that are easy to store, so that computers can process various image information like the human brain. And then replace humans to complete some work related to visual information. Target tracking refers to estimating the motion state of the target by determining the position information of the target in the video image, and predicting its motion characteristics in the next frame at the same time, and then matching the target in the video according to the acquired features, so as to achieve The purpose of continuous and accurate tracking of the target. As far as the current target tracking methods are concerned, they can be divided into two categories according to whether they rely on prior knowledge, namely, target-dependent prior knowledge and target-independent prior knowledge. The former needs to model the target, and then perform template matching in the subsequent image sequence to find the target of interest. The latter can directly detect the moving target from the image sequence, combined with the corresponding search algorithm to achieve effective tracking of the moving target.

Contents of the invention

In view of the above defects, the present invention studies the optical flow method and Kalman filter. Among them, the optical flow method is an approximate estimate of the real motion field. Under ideal conditions, it can detect independently moving targets without knowing any information about the scene in advance. In addition, because the time interval between consecutive frames is very short, the motion of each moving target can be approximated as a uniform motion, and Kalman filtering is an algorithm that uses state equations and observation equations to perform linear minimum variance estimation on the state sequence of the system. It makes an optimal estimate for the next state based on the previous state sequence of the system. It has the characteristics of unbiased, stable, optimal, and small amount of calculation when predicting, and can accurately predict the position and speed of the target. Therefore, the present invention combines the advantages of the Lucas-Kanade optical flow method based on the image pyramid and the Kalman filtering method to fuse them for target tracking, and uses an improved median filtering algorithm to filter the acquired images in the process so that Obtain the tracked target more accurately.

In order to achieve the above object, the present invention adopts the following technical scheme: the multi-target tracking method based on optical flow method and Kalman filter, comprising the following steps:

(1) Read the video frame, and use the L-K optical flow method based on the image pyramid to calculate the optical flow of each frame of image.

(2) Perform clustering processing on the optical flow to obtain several optical flow classes, and obtain an optical flow detection effect map marked with optical flow information.

(3) The improved median filter method is used to denoise the optical flow detection effect map.

(4) The number of optical flow classes is the number of moving targets, and the information of these moving targets is passed to the Kalman filter for target tracking processing.

In the above scheme, the specific process of the L-K optical flow method based on the image pyramid includes: calculating the optical flow on the image of the highest layer; using the result of the calculation as the initial value of the image of the next layer, and in this initial value Calculate the optical flow of this layer on the basis; repeat this process until it is passed to the last layer, the original image layer.

In a specific embodiment of the present invention, the calculation method of the light flow is:

Define the following function on a local neighborhood centered on point a, and minimize the function value:

Among them, Ω represents the local neighborhood of point a, W(x, y) represents the weight function, Represents the gradient of the image at point a, V _a represents the optical flow of point a, I _t represents the gray value of point a=(x, y) I=(x, y, t) the time domain of the image at time t Derivative.

By optimizing the above formula, we can get:

A column vector representing the gradient of n points;

W=diag[W(x ₁ ),W(x ₂ ),...,W(x _n )] represents a diagonal matrix containing weights of n points;

b=-[I _t (x ₁ ), I _t (x ₂ ),...,I _t (x _n )] ^Τ represents a vector comprising time-domain derivatives of n points at time t;

V=[A ^Τ W ² A] ^-1 A ^Τ W ² b represents the optical flow information sought;

Represents the gradient of the image at the nth point, W(x _n ) represents the window weight of the image at the nth point, I _t (x _n ) the temporal derivative of the gray value of the nth point of the image at time t , where x _i ∈Ω and i=1,2,3...n.

The clustering process includes: setting a threshold D _th , comparing the metric function D of two optical flow vectors, if the metric value is less than the threshold, merging the two optical flows as an optical flow class, and calculating the optical flow The average optical flow of the class; then compare the other optical flow vectors with the average optical flow metric function and the threshold value, and if it is less than the threshold value, the optical flow will be incorporated into the optical flow class.

In the same optical flow class, if the distance d _i ≥ (μ+2σ) from a point ( _xi , y _i ) to the center of this optical flow class, delete this point.

d _i ＝(x _i -c _x ) ² +(y _i -c _y ) ²

n represents the total number of pixels in the same optical flow class. In addition, μ is the mean value, also called expectation, and it is also the position parameter of the normal distribution, which describes the central tendency position of the normal distribution, and the normal distribution is symmetrical with x=μ. σ represents the standard deviation of a random variable and also represents the degree of dispersion of normally distributed data. The larger the σ, the more dispersed the data, and the smaller the σ, the more concentrated the data. At the same time, σ is also the shape parameter of the normal distribution curve, the larger the value, the flatter the distribution curve, and the smaller the value, the higher the curve.

The above measurement function D is

(u ₁ , v ₁ ) and (u ₂ , v ₂ ) denote two optical flow vector values respectively.

Specifically, the step (3) also includes the following steps: converting the optical flow detection effect map into a grayscale image; denoising the grayscale image through an improved median filter; converting the denoised image into a binary image Valued images; the final moving target is obtained through expansion processing and morphological closing operations.

Further, the improved median filtering adopts a fast parallel median filtering method: after calculating the maximum value, median value and minimum value for each column or row in the sliding window, the row number or column array data of the sliding window is obtained; The maximum value of the window is the maximum value in the maximum value group, the minimum value of the sliding window is the minimum value in the minimum value group, and the median value of the sliding window is the minimum value in the maximum value group, the median value in the median value group, and The middle value of the three numbers that is the maximum value in the minimum group.

The advantages of the present invention are as follows: firstly, a method that does not depend on the prior knowledge of the target is adopted, so there is no need to train a classifier and construct a target template. Second, the optical flow method can capture moving objects well, and can better mark moving objects with optical flow information after clustering. Third, by improving the processing of the median filter, part of the noise can be filtered out very well, and it is nearly 2 times faster than the traditional median filter. The last is to combine the continuous iteration of the prediction and correction process of Kalman filter to achieve dynamic balance and fast iteration speed, and can achieve good tracking effect.

Description of drawings

Fig. 1 is a specific flow chart of the present invention;

Figure 2 is the processed optical flow diagram of the moving target;

Figure 3 is the median filtering effect;

Figure 4 is a partial tracking effect diagram.

detailed description

Embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings.

The algorithm flow of the method of the present invention is shown in FIG. 1 . The specific implementation process is as follows:

Step 1: Process the read video frames using the image pyramid-based Lucas-Kanade optical flow method. When the light source shines on the surface of the object, the gray scale of the surface will show a certain spatial distribution. When people observe a moving object, a continuously changing image will be formed on the retina, which is the optical flow. Optical flow expresses the change of the image, contains the information of the moving target, and can be used to determine the movement of the target.

L-K optical flow first assumes that the motion vector remains constant over a small spatial neighborhood, and then uses weighted least squares to estimate the optical flow field. Assuming that the gray value of point a=(x,y) at time t is I=(x,y,t), the optical flow constraint equation can be derived:

in, u and v are the horizontal and vertical components of the optical flow at this point, which represent the motion information of the target, and formula (1) is simplified:

I _x u + I _y v + I _t = 0 (2)

I _x , I _y represent the spatial gradient field of the gray value of point a=(x, y) I=(x, y, t) in the direction of x-axis and y-axis respectively, I _t represents point a=(x, The gray value of y) is the time-domain derivative of the I=(x, y, t) image at time t.

Write formula (2) in the form of formula (3): use the gradient vector at point a The dot product of the optical flow vector V _a of point a and the sum of I _t is zero to represent:

in, Represents the gradient of the image at point a; V _a =(u, v) is the optical flow of point a. Assuming that in a local neighborhood centered on point a, the optical flow of each point is the same, and the search displacement should minimize the matching error of the relevant neighborhood of the corresponding point, that is, define a function on this neighborhood as formula (4), and minimize its function value:

Among them, Ω represents the local neighborhood of point a, and W(x, y) represents the window weight function, which makes the central part of the neighborhood have a greater influence on the optical flow constraints than the peripheral part. By optimizing and solving formula (4), we can get:

A column vector representing the gradient of n points;

W=diag[W(x ₁ ),W(x ₂ ),...,W(x _n )] represents a diagonal matrix containing weights of n points;

b=-[I _t (x ₁ ), I _t (x ₂ ),...,I _t (x _n )] ^Τ represents a vector comprising time-domain derivatives of n points at time t;

V=[A ^Τ W ² A] ^-1 A ^Τ W ² b represents the optical flow information sought;

Represents the gradient of the image at the nth point, W(x _n ) represents the window weight of the image at the nth point, I _t (x _n ) the temporal derivative of the gray value of the nth point of the image at time t , where x _i ∈Ω and i=1,2,3...n.

If the L-K optical flow method is used alone, although the optical flow can be obtained and it is not sensitive to noise, when the target motion scale is too large or occlusion occurs, large calculation errors will occur due to the large motion scale, not only It will affect the accuracy of the algorithm and also reduce the overall computing speed. For this, the present invention adopts the L-K optical flow method based on the pyramid, and its principle is described as follows: first, the optical flow and the affine transformation matrix are calculated on the image of the highest layer. The initial value of the image of the next layer is the calculation result of the previous layer, and the image of the next layer calculates the optical flow and affine transformation matrix of this layer on the basis of this initial value. This process is then repeated until passed to the last layer, the original image layer. The final result is the optical flow and affine transformation matrix calculated on the original image layer, and finally realizes the screening process from coarse to fine.

Step 2: The basis for clustering the optical flow is that the optical flow on the same moving target is approximate and its distribution presents a certain regularity, while the optical flow on different targets is different, and several classes can be obtained. Assuming that there are two optical flow vector values (u ₁ , v ₁ ) and (u ₂ , v ₂ ), the metric function to measure their similarity is set as follows:

Optical flow clustering can be divided into coarse clustering and fine clustering. A small threshold D _th needs to be set for rough clustering, and the metric function D of the two optical flow vectors is compared. If the metric value is less than the set threshold, the two optical flows are merged, and the average optical flow of this class is calculated. . When judging whether other optical flow vectors are incorporated into a certain class, it is necessary to measure the size of the metric function value between them and the average optical flow of the class. In addition, several optical flow classes that have been obtained need to be processed during fine clustering. However, due to the existence of various noises, there may be some outliers in each class, so it is necessary to remove the outliers. Suppose the pixels in a certain optical flow class are: (x ₁ ,y ₁ ),(x ₂ ,y ₂ ),...,(x _n ,y _n )

Since the distance from the points in the same class to the center of the class obeys the normal distribution with parameters (μ, σ), if the distance d _i ≥ (μ+2σ) from a point ( _xi , y _i ) to the center of the class, then Delete the point, where the parameters are as follows:

d _i ＝(x _i -c _x ) ² +(y _i -c _y ) ²

n represents the total number of pixels in the same class. In addition, μ is the mean value, also called expectation, and it is also the position parameter of the normal distribution, which describes the central tendency position of the normal distribution, and the normal distribution is symmetrical with x=μ. σ represents the standard deviation of a random variable and also represents the degree of dispersion of normally distributed data. The larger the σ, the more dispersed the data, and the smaller the σ, the more concentrated the data. At the same time, σ is also the shape parameter of the normal distribution curve, the larger the value, the flatter the distribution curve, and the smaller the value, the higher the curve.

The moving target can be clearly marked by the optical flow information after processing, and the effect diagram is shown in Figure 2.

Step 3: The image processing technology is highly targeted, and the processing methods are different due to different applications and requirements. In addition, there are many factors that affect image changes, such as: weather, light, camera shake, various noises, etc., so it is necessary to denoise the image. The present invention selects the median filtering method for denoising. First of all, in this process, instead of processing the optical flow, the image of the optical flow detection effect map (as shown in Figure 2) is converted into a grayscale image. Second, the grayscale image is denoised by median filtering. The denoised image is then converted into a binarized image. Finally, the final goal is obtained through dilation processing and morphological closing operations. Under certain conditions, the median filter can deal with the fuzzy image details produced by the linear filter, especially for the processing of scanning noise or filtered pulses.

The traditional median filter uses a sliding window with odd points, and replaces the gray value of the specified point with the median value of the gray value of each point in the window. For odd-numbered elements, the median value is the middle value after size sorting. For even-numbered elements, the median value is the average value of the gray values of the middle two elements after sorting, and the sorting algorithm is the key to median filtering. The traditional algorithm uses the bubble sorting method. Assuming that the number of pixels in the window is m, each window needs to be compared m(m-2)/2 times, and the time complexity is O(m ² ). In addition, sorting is performed every time the window is moved, and when the size of the image is N*N, the time complexity is O(m ² N ² ). When the image is large, the amount of calculation is large and time-consuming. For this, the present invention uses a fast parallel median filtering method. For the sake of illustration, assume a 3*3 window, and its internal pixels are shown in Table 1:

Table 1 Each pixel in the 3*3 window

pixel column 1 column 2 column 3 line 1 line 2 line 3

After calculating the maximum value, median value and minimum value for each column in the window, three sets of data are obtained. Among them, max means to take the maximum value, med means to take the median value, and min means to take the minimum value.

Maximum group: Max1=max[F ₀ ,F ₃ ,F ₆ ], Max2=max[F ₁ ,F ₄ ,F ₇ ], Max3=max[F ₂ ,F ₅ ,F ₈ ]

Median group: Med1 = med[F ₀ , F ₃ , F ₆ ], Med2 = med[F ₁ , F ₄ , F ₇ ], Med3 = med[F ₂ , F ₅ , F ₈ ]

Minimum value group: Min1=min[F ₀ ,F ₃ ,F ₆ ], Min2=min[F ₁ ,F ₄ ,F ₇ ], Min3=min[F ₂ ,F ₅ ,F ₈ ]

The maximum value in this sliding window is the maximum value in the maximum value group, and the minimum value is the minimum value in the minimum value group. And the smallest value in the median group is at least smaller than 5 pixel values, and the largest value in the median group is at least larger than 5 pixel values. At this point, there are 3 pixels to be compared: the minimum value in the maximum value group, the median value in the median value group, and the maximum value in the minimum value group, and the median value of these three numbers is the median value of the window. value, whose expression is as follows:

MininMax＝min[Max1,Max2,Max3]

MedinMed = med[Med1, Med2, Med3]

MaxinMin=max[Min1,Min2,Min3]

Med = med[MininMax, MedinMed, MaxinMin]

Compared with the traditional algorithm, the calculation speed of this median filtering method is increased by nearly 2 times. The effect diagram after processing is shown in Figure 3. The white connected area in the figure is the moving target, and the black area is the background area.

Step 4: After the above process, through optical flow clustering, the number of classes obtained is the number of moving objects. The average value of the optical flow vector in the class is obtained as the speed of the moving target. Pass the detected moving target information to the Kalman filter for subsequent tracking processing. Kalman filtering is based on state equations and observation equations, and uses recursive methods to predict linear system changes. Its state equation and observation equation are as follows: x _k ＝A _k,k-1 x _k-1 +ξ _k-1 (6)

z _k ＝H _k z _k +η _k (7)

Among them, x _k-1 and x _k represent the state vectors at time k-1 and time k respectively; z _k represents the observation vector at time k; A _k,k-1 represents the state transition matrix from time k-1 to time k ; H _k represents the observation matrix; ξ _k or ξ _k-1 represents the system noise at different times, and ξ _k ∈ N(0, Q _k ); η _k represents the observation noise, and η _k ∈ N(0, R _k ); Q _k and R _k are the variances of system noise ξ _k and observation noise η _k , respectively. Kalman filtering can be summarized as a state prediction process and a state correction process, involving the following parts:

State vector prediction equation:

Error covariance prediction equation:

Kalman filter gain:

Corrected state vector:

Corrected error covariance matrix: P _k ＝P _k,k-1 -K _k H _k P _k,k-1 (12)

Among them, formula (8) and formula (9) are the state prediction process, and formula (9), formula (10) and formula (11) are the state correction process. The prediction is based on the state equation (6), and the state prediction vector is obtained and error covariance prediction vector P _k,k-1 . The correction is based on the observation equation (7), and the state prediction vector is corrected to obtain the vector And calculate the minimum error covariance matrix.

The motion between objects in adjacent frames in the video can be approximated as uniform motion, and the kinematics formula is as follows, where △t is the time interval between adjacent frames:

S _k ＝S _k-1 +△tV _k-1 (13)

_{Vk = Vk-1} (14)

S _k represents the displacement of the target after the time interval △t, and V _k represents the current speed of the target. Since it is approximately uniform motion, the speed is basically the same at each moment.

The state vector of the Kalman filter is as follows:

Among them, x(k) and y(k) are the coordinates of the center point of the moving target, and V _x (k) and V _y (k) are the velocity components of the target center in the direction of the two coordinate axes. Therefore, its state transition matrix is as follows:

According to the coordinate information of the target center point, the observation vector and observation matrix can be obtained as follows, x _z (k) and y _z (k) represent the coordinates of the center point of the rectangular frame marking the target in the kth frame:

After putting equations (15) to (18) into equations (6) and (7), the state equation and observation equation can be re-described. Among them, ξ _k-1 and η _k are 4*1-dimensional and 2*1-dimensional system noise and observation noise, respectively, and they are also Gaussian white noise with a mean value of 0. The covariance matrices Q and R of the system noise and observation noise are set as follows:

Set the variance of the two components of the observation noise in equation (20) Then the observation noise covariance matrix R is the identity matrix. In addition, the initial value of the error covariance matrix can be set as follows:

Because the motion of the target in adjacent frames can be approximated as uniform motion, for the convenience of calculation, the inter-frame interval △t=1, then the initial value of the state vector can be expressed as follows:

x ₀ is the initial state of the Kalman filter, x(0) and y(0) represent the center point coordinates of the target in the initial state, x(k)-x(k-1) and y(k)-y(k -1) represent the displacements in the x-axis direction and the y-axis direction at the Kth time and the K-1th time, respectively.

Kalman filter tracking is to seek a dynamic balance in the continuous iterative process of state prediction and state correction. When the number of iterations reaches the set value or obtains a local optimum, the final result is output. Part of the effect diagram is shown in Figure 4.

Step 5: Determine whether the video is over. Suppose there are N frames of the video to be processed, and the current frame number is i, by judging the size of the current frame number i and N. If i is less than N, that is, the video is not over, then go to step 1, and then continue to repeat the above process in a loop. If i is greater than or equal to N, it means that the video has been processed and the program ends.

Claims (8)

1. The multi-target tracking method based on the optical flow method and Kalman filtering comprises the following steps:

(1) reading video frames, and calculating the optical flow of each frame of image by adopting an L-K optical flow method based on an image pyramid;

(2) clustering the optical flow to obtain a plurality of optical flow classes, and obtaining an optical flow detection effect graph marked with optical flow information;

(3) denoising the optical flow detection effect graph by adopting an improved median filtering method;

(4) the number of the optical flow types is the number of the moving targets, and the information of the moving targets is transmitted to Kalman filtering for target tracking processing.

2. The multi-target tracking method based on the optical flow method and the Kalman filtering as claimed in claim 1, characterized in that: the specific process of the L-K optical flow method based on the image pyramid comprises the following steps: calculating an optical flow on the image of the highest layer; taking the calculated result as an initial value of the image of the next layer, and calculating the optical flow of the layer on the basis of the initial value; this process is repeated until the last layer, the original image layer, is passed.

3. The multi-target tracking method based on the optical flow method and the Kalman filtering as claimed in claim 2, characterized in that: the optical flow calculation method comprises the following steps:

defining the following function on a local neighborhood centered on point a and minimizing the function value:

$F(x,y)=\underset{(x,y)\∈\mathrm{\Ω}}{\Σ}{W}^2(x,y)\[\▿I\·V_a+I_t\]$

where Ω represents the local neighborhood of point a, W (x, y) represents a weight function,representing the gradient, V, of the image at point a_aOptical flow representing point a, I_tThe gray value representing point a ═ x, y is the time-domain derivative of the (x, y, t) image at time t;

the optimization solution of the above equation can be obtained:

a column vector representing a gradient containing n points;

W＝diag[W(x₁),W(x₂),...,W(x_n)]representing a diagonal matrix containing weights of n points;

b＝-[I_t(x₁),I_t(x₂),...,I_t(x_n)]^Τa vector representing the time-domain derivative containing n points at time t;

V＝[A^ΤW²A]^-1A^ΤW²b represents the optical flow information obtained;

representing the gradient of the image at the nth point, W (x)_n) Representing the window weight, I, of the image at the nth point_t(x_n) Time-domain derivative of the gray value of the nth point of the image at time t, where x_i∈ Ω and i ═ 1,2,3.. n.

4. The multi-target tracking method based on the optical flow method and the Kalman filtering as claimed in claim 1, characterized in that: the clustering process includes: setting a threshold value D_thComparing the measurement functions D of the two optical flow vectors, merging the two optical flows if the measurement value is smaller than a threshold value to be used as an optical flow class, and calculating the average optical flow of the optical flow class; the metric functions of the remaining optical flow vectors and the average optical flow are then compared with a threshold value, and if the metric functions are smaller than the threshold value, the optical flow is incorporated into the optical flow class.

5. The method of claim 4The multi-target tracking method based on the optical flow method and Kalman filtering is characterized in that: also included in the same class of optical flow, if a certain point (x)_i,y_i) Distance d from the center of the natural flow class_iIf the value is more than or equal to (mu +2 sigma), deleting the point;

d_i＝(x_i-c_x)²+(y_i-c_y)²

n represents the total number of pixels in the same optical flow class.

6. The multi-target tracking method based on the optical flow method and the Kalman filtering according to claim 4 or 5, characterized in that: the metric function D is

$D(u_1,v_1;u_2,v_2)=\frac{\sqrt{{(u_1-u_2)}^2+{(v_1-v_2)}^2}}{0.5\·(\sqrt{u_1^2+v_1^2}+\sqrt{u_2^2+v_2^2})}$

(u₁,v₁) And (u)₂,v₂) Representing two optical flow vector values, respectively.

7. The multi-target tracking method based on the optical flow method and the Kalman filtering as claimed in claim 1, characterized in that: the step (3) further comprises the following steps: converting the optical flow detection effect graph into a gray scale graph; denoising the gray level image through improved median filtering; converting the denoised image into a binary image; and acquiring a final moving target through the expansion processing and the morphological closing operation.

8. The multi-target tracking method based on the optical flow method and the Kalman filtering as recited in claim 7, characterized in that: the improved median filtering adopts a fast parallel median filtering method: respectively calculating the maximum value, the median value and the minimum value of each column or each row in the sliding window to obtain row number or column group data of the sliding window; the maximum value of the sliding window is the maximum value in the maximum value group, the minimum value of the sliding window is the minimum value in the minimum value group, and the median of the sliding window is the median of three values, namely the minimum value in the maximum value group, the median in the median group and the maximum value in the minimum value group.