CN101770568A - Target automatically recognizing and tracking method based on affine invariant point and optical flow calculation - Google Patents

Abstract

The invention discloses an automatic target recognition and tracking method based on affine invariant points and optical flow calculation. First, image preprocessing is performed on the target image and video frame, and the affine invariant feature points are extracted, and then the feature points are matched, and the incorrectly matched points are eliminated. When the matching pairs of feature points reach a certain number, and affine can be generated When transforming the matrix, confirm that the target recognition is successful. Then use the affine invariant points collected in the previous step to perform characteristic optical flow calculations to realize real-time target tracking; if the intermediate target is lost, immediately return to the first step and perform target recognition again. The feature point operator used in the present invention is a scale-space-based image local feature description operator that maintains invariance to image scaling, rotation, and even affine transformation; and the feature optical flow calculation method adopted has a small amount of calculation , High accuracy, can realize real-time tracking. The invention is widely used in the fields of video surveillance, image search, computer-aided driving system, robot and the like.

Description

Automatic Target Recognition and Tracking Method Based on Affine Invariant Point and Optical Flow Calculation

technical field

The invention relates to a method in the technical field of image processing, in particular to an automatic target recognition and tracking method based on affine invariant points and optical flow calculation.

Background technique

Target recognition and tracking technology is widely used in various systems, such as video surveillance systems, image search systems, medical image systems, computer-assisted driving systems, robots, smart rooms, etc. Real-time and stable identification and tracking of moving targets is a very difficult task, because image noise, blur, and illumination changes brought about by the increasingly complex external environment have brought great difficulties to target recognition. At the same time, tracking The attitude and scale of the target will change at any time during the process, which will affect the stability of the recognition and tracking algorithms.

The main task of target recognition is to extract the target of interest through image data and identify it. At present, target recognition methods are mainly divided into bottom-up data-driven and top-down knowledge-driven. The top-down knowledge-based target recognition method for specific types of targets in the image has the disadvantages of poor substitution and compatibility, and the recognition target changes, and the knowledge needs to change accordingly. The bottom-up data-driven target recognition method does not consider the type of the target, and performs low-level processing on the image, which is widely applicable and has strong substitution. The present invention adopts a bottom-up target recognition method.

Tracking the target on the basis of successful recognition will get a better tracking effect. Target tracking methods can be divided into methods based on motion analysis and methods based on image matching according to whether inter-frame information is used. The tracking method based on motion analysis relies entirely on motion detection to track moving objects, and the typical frame difference method and optical flow method are more typical. Optical flow tracking uses the different speeds between the target and the background to detect moving targets, which has better anti-noise ability. Optical flow methods can be divided into continuous optical flow methods and characteristic optical flow methods. The characteristic optical flow method is to obtain the optical flow at the feature point through the feature matching of the sequence image, and realize the separation of the target and the background through the optical flow clustering. The advantage of the characteristic optical flow method is that it can handle large inter-frame displacements, reduce the sensitivity to noise, only process a small number of feature points in the image, and have a small amount of calculation. The present invention adopts a target tracking method based on the characteristic optical flow method.

Invention content:

The purpose of the present invention is to provide a method for quickly and accurately identifying a target and performing real-time target tracking.

The technical solution to realize the object of the present invention is a target recognition and tracking method based on affine invariant points and optical flow calculation, the steps of which are:

The first step, target recognition: first, image preprocessing is performed on the target image and video frame, and affine invariant feature points are extracted, then feature point matching is performed, and incorrectly matched points are eliminated. When the matching pairs of feature points reach a certain When the number and the affine transformation matrix can be generated, it is confirmed that the target recognition is successful.

The feature points extracted in this step remain invariant to image scale and rotation, and are robust to light changes, noise, and affine changes.

The second step, target tracking: use the affine invariant points collected in the previous step to perform characteristic optical flow calculations to realize real-time target tracking; if the intermediate target is lost, immediately return to the first step and perform target recognition again.

Compared with the prior art, the present invention has the following significant advantages: 1. The feature point operator used in the present invention is a scale-space-based image local feature description algorithm that maintains invariance to image scaling, rotation, and even affine transformation. Its matching accuracy is high, and it can still accurately match a large number of stable points when the image has more complex deformation (including geometric deformation, resolution change and illumination change, etc.); 2. The present invention uses characteristic optical flow The target tracking method can handle large inter-frame displacements, and the sensitivity to noise is reduced. Only a few feature points in the image are processed, and the amount of calculation is small.

Description of drawings:

FIG. 1 is a flowchart of the target recognition and tracking method based on affine invariant points and optical flow calculation of the present invention.

Fig. 2 is a target image of the target recognition and tracking method based on affine invariant points and optical flow calculation of the present invention.

FIG. 3 is a screenshot of a successful target recognition and tracking video of the target recognition and tracking method based on affine invariant points and optical flow calculation of the present invention.

Detailed ways:

The specific content of the present invention will be further described below in conjunction with the accompanying drawings.

The invention discloses a method for automatic target recognition and tracking based on affine invariant points and optical flow calculation. The method includes the following steps:

The first step, target recognition: first, perform image preprocessing on the target image and the first frame of the video, and extract affine invariant feature points, then perform feature point matching, and eliminate incorrectly matched points. When the number reaches a certain amount and an affine transformation matrix can be generated, it is confirmed that the target recognition is successful. If the target recognition is unsuccessful, the next frame of the video is sequentially matched with the target image until the target recognition is successful;

The second step, target tracking: use the affine invariant points collected in the current frame of the video to calculate the characteristic optical flow, find the position of the invariant points in the next frame, and realize real-time target tracking; if the intermediate target is lost, immediately return to the first One step, re-identify the target;

The idea of this algorithm is to first extract the affine invariant points in the image and the video frame for matching, so as to identify the target and determine the position of the target in the video frame, and then use these feature points to perform optical flow calculations to achieve real-time tracking of the target. track.

The present invention is based on affine invariant points and the target automatic identification and tracking method of optical flow calculation, and the steps of extracting affine invariant feature points in the process of target recognition are as follows:

The first step is to use the Gaussian convolution kernel to smooth the target image and video frame, using the following formula

L(x,y,σ)=G(x,y,σ)*f(x,y)

$\mathrm{<span\; class="notranslate">\; G</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; \&sigma;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;\&sigma;</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span>\frac{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}}$

Among them, L(x, y, σ) is the image whose scale space is σ after smoothing, G(x, y, σ) is the Gaussian function, and f(x, y) is the original image;

在高斯金字塔中每阶相邻两个高斯图像作差即得到高斯差分(DoG)金字塔。取金字塔第一阶第一层图像尺度坐标

金子塔的总阶数为log₂(min(w，h))-2，其中w为原始图像宽度，h为原始图像高度；The second step is to establish an image scale space pyramid. The original image is doubled first, and this image is used as the first-order image prototype of the Gaussian scale space pyramid. After that, the image prototype of each order is down-sampled from the previous-order image prototype, and the size is the size of the previous-order prototype.

In the Gaussian pyramid, the difference between two adjacent Gaussian images at each level is the difference of Gaussian (DoG) pyramid. Take the image scale coordinates of the first level and the first layer of the pyramid

The total order of the pyramid is log ₂ (min(w, h))-2, where w is the original image width and h is the original image height;

The third step is to compare each pixel in the image to be detected with the 2×9 pixels adjacent to the upper and lower images of the same order, and the 8 pixels around itself to find the extreme point and determine is a candidate feature point;

The fourth step is to remove some low-contrast feature points and unstable edge response points. Fitting three-dimensional quadratic function is used to refine the DoG function value of feature points and remove low-contrast feature points. If the pixel values in the DoG image are normalized between [0, 1], all The points are judged as low-contrast candidate extremum points and filtered out. Use the feature points at the edge of the image to have a large main curvature value at the intersection of the peak of the Gaussian difference image and the edge, but the curvature in the vertical direction is small to filter out the low-contrast feature points at the edge;

The fifth step is to determine the direction of the feature points. For an image f(x, y), the modulus and direction of the gradient at the pixel point (x, y) are calculated as follows:

$\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}$

$\mathrm{<span\; class="notranslate">\; \&theta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; arctan</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span>$

Sampling in the neighborhood window (neighborhood window size = 3×1.5×feature point scale) centered on the feature point, and use the histogram to count the gradient direction of the neighborhood pixels. In the gradient direction histogram, when there is another peak equivalent to 80% of the energy of the main peak, this direction is considered as the auxiliary direction of the feature point;

The sixth step is to generate feature point description words. First, rotate the coordinate axis to the direction of the feature point, then take a 16×16 window centered on the feature point, calculate the gradient direction histogram of 8 directions on each 4×4 small block, and obtain the gradient direction histogram of each gradient direction Accumulate the value to form a seed point, so that a 128-dimensional feature vector can be generated for a feature point. Continue to normalize the length of the feature vector;

The feature point operator obtained in this way is based on scale space, maintains invariance to image scaling, rotation and even affine transformation, and can accurately match a large number of stable points in the case of images with complex deformations. Local feature description operator.

The present invention is based on an affine invariant point and an optical flow calculation target automatic identification and tracking method, and the steps of feature point matching in the target identification process are as follows:

In the first step, if there are m feature points in the target image, the description word array is (A ₁ , A ₂ , ..., A _m ), and there are n feature points in the image to be matched, and the description word array is (B ₁ , B ₂ ,..., B _n ), build a kd tree for (A ₁ , A ₂ ,..., A _m ), and use the BBF (Best-Bin-First) algorithm to search for B _j (j =1,...,n) neighbor feature point A _i (i=1,...,m). For example, the Euclidean distance between two feature point descriptors A(a ₀ , a ₁ ,...,a ₁₂₇ ) and B(b ₀ , b ₁ ,...,b ₁₂₇ ) is:

$\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; =</span>\sqrt{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 127</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}$

When the feature points of two images describe the minimum Euclidean distance d between words, these two feature points are the nearest neighbor feature points, and they are called a pair of matching points;

The second step is to use the RANSAC (RANdom SAmple Consensus) random sampling consensus algorithm to eliminate mismatched feature points. The steps are:

(1) Randomly select 4 feature matching pairs (A ₁ , B ₁ ), (A ₂ , B ₂ ), (A ₃ , B ₃ ), (A ₄ , B ₄ ), and calculate the corresponding homography matrix H

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; =</span>\left[\begin{array}{ccc}{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 11</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 12</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 13</span>}}\\ {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; twenty\; one</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; twenty\; two</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; twenty\; three</span>}}\\ {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 31</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 32</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 33</span>}}\end{array}\right]$

(2) The point corresponding to the feature point A _i (i=1,...,4) with this matrix is C _i , if the Euclidean distance d between A _i and C _i is less than the error threshold, go to step 3, Otherwise, go to step 1;

(3) To detect whether H is satisfied for all possible feature matching pairs, divide all data into "inside point" and "outside point";

(4) Repeat the above steps 1-3 N times;

(5) Find the feature matching pairs that satisfy the maximum number of points in the corresponding matrix calculated by each iteration, these points are the correct matching points, and calculate the final homography matrix H;

The number of correctly matched feature points must be more than 4, that is, the homography matrix H can be obtained, indicating that the target recognition is successful, otherwise the next frame and the target image are sequentially taken for target recognition.

The present invention is based on affine invariant point and optical flow calculation target automatic recognition and tracking method, the steps of target tracking are as follows:

The first step is to establish the window W to be tracked by the affine invariant feature points obtained by target recognition, calculate the sum of squared gray difference SSD (Sum of Squared intensity Differences) between video image frames, move the feature window, and repeat several steps until s is less than a certain threshold, at this time, it is considered that the feature windows of the two frames are successfully matched, that is, the position of the corresponding feature point is found in the next frame;

The second step is to use the RANSAC (RANdom SAmple Consensus) random sampling consensus algorithm to calculate the homography matrix H of the next frame of image

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; =</span>\left[\begin{array}{ccc}{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 11</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 12</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 13</span>}}\\ {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; twenty\; one</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; twenty\; two</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; twenty\; three</span>}}\\ {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 31</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 32</span>}}& {\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; 33</span>}}\end{array}\right]$

If H can be obtained at last, it is considered that the target tracking is successful, and those feature points that do not conform to the homography matrix are eliminated, and the target tracking of the next frame is entered; if H cannot be obtained, it means that the target is lost, and the target recognition is performed again.

In conjunction with Fig. 1, a kind of target automatic identification and tracking method based on affine invariant point and optical flow calculation of the present invention, the steps are as follows:

The first step, target recognition:

The target image f(x, y) with width w and height h, using the formula

L(x,y,σ)=G(x,y,σ)*f(x,y)

$\mathrm{<span\; class="notranslate">\; G</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; \&sigma;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;\&sigma;</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span>\frac{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}}$

金子塔的总阶数为log₂(min(w，h))-2。将图像中每个像素点与同阶上、下层两幅图像相邻的2×9个像素点，以及自己周围的8个像素点进行比较，找寻极值点，确定为候选特征点。采用拟合三维二次函数来精确特征点的高斯差分函数值并去除低对比度的特征点，同时去掉不稳定的边缘响应点。Perform Gaussian smoothing. Then the original image is doubled, and this image is used as the first-order image prototype of the Gaussian scale space pyramid. After that, the image prototype of each order is obtained by downsampling the image prototype of the previous order, and the size is the size of the previous-order prototype.

The total order of the pyramid is log ₂ (min(w,h))-2. Compare each pixel in the image with the adjacent 2×9 pixels of the upper and lower images of the same order, and the 8 pixels around itself, find the extreme points, and determine them as candidate feature points. Fitting a three-dimensional quadratic function is used to refine the Gaussian difference function value of feature points and remove low-contrast feature points, while removing unstable edge response points.

Use the modulus and direction of the gradient at the point (x, y) to find the formula

$\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}$

$\mathrm{<span\; class="notranslate">\; \&theta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; arctan</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span>$

Obtain the direction and modulus of the feature points. Then rotate the coordinate axis to the direction of the feature point, take a 16×16 window centered on the feature point, and generate a 128-dimensional feature vector from the accumulated value of each gradient direction, and normalize the length of the feature vector.

Perform the same processing on the first frame of the video, extract the feature points, and obtain the 128-dimensional feature vector of each feature point.

最小时，得到一对匹配点。搜索到所有的匹配点后，利用RANSAC(RANdom SAmple Consensus)随机抽样一致性算法消除错配特征点，正确匹配的点对大于4个，并能计算出单应性矩阵H，从而目标在视频帧中的位置识别成功，否则识别失败，在视频下一帧中重复识别目标。Build a kd tree with the feature points of the target image, use the BBF (Best-Bin-First) algorithm to search for the feature points on the video frame, and require the Euclidean distance between the two point feature vectors

At minimum, a pair of matching points is obtained. After searching all the matching points, use the RANSAC (RANdom SAmple Consensus) random sampling consensus algorithm to eliminate the mismatched feature points. The correct matching point pairs are more than 4, and the homography matrix H can be calculated, so that the target is in the video frame The position recognition in is successful, otherwise the recognition fails, and the recognition target is repeated in the next frame of the video.

The second step, target tracking:

The window W to be tracked is established by the affine invariant feature points obtained from the target recognition of this frame, and the KLT (Kanade Lucas Tomasi) algorithm is used to calculate the sum of squares of the gray level difference SSD (Sum of Squared intensity Differences) between this frame and the next frame of video images, Move the feature window in the next frame image, match it with the feature window of the previous frame, find the position of the corresponding feature point, if not found, remove those missing feature points.

Then use the random sampling consensus algorithm (RANSAC Random Sample Consensus) to remove the mismatched points from the feature points found in the next frame of image, and generate a homography matrix. If the number of remaining correctly matched points is greater than 4, and the homography matrix can be successfully generated, it means that the target tracking is successful; otherwise, it means that the target has been lost. Immediately return to the first step, and use the next frame image as the current frame to start the target again. identify.

Fig. 2 is a target image of the target recognition and tracking method based on affine invariant points and optical flow calculation of the present invention, and Fig. 3 is a video screenshot of successful target recognition and tracking.

Claims (4)

1. the target based on affine invariant point and optical flow computation is discerned and tracking automatically, and this method comprises the steps:

The first step, Target Recognition: at first target image and video first frame are carried out the image pre-service, and extract affine invariant features point, carry out Feature Points Matching then, and weed out the point of mistake coupling, when the coupling of unique point to reaching some, and can generate affine transformation matrix the time, confirm the Target Recognition success.If Target Recognition is unsuccessful, next frame and the target image of getting video successively mate, up to the Target Recognition success;

Second step, target following: the affine invariant point of utilizing this frame of video to collect, carry out characteristic light stream and calculate, find down the position of invariant point in the frame, realize real-time target following; With losing, return the first step as intermediate objective at once, carry out Target Recognition again;

The thought of this algorithm is that the affine invariant point of at first extracting in image and the frame of video is mated, thereby Target Recognition is come out and determines the position of target in frame of video, utilizes these unique points to carry out optical flow computation then, realizes object real-time tracking.

2. the target based on affine invariant point and optical flow computation according to claim 1 is identification and tracking automatically, and the step that it is characterized in that extracting affine invariant features point is as follows:

The first step utilizes Gaussian convolution to check target image and frame of video is carried out smoothing processing, adopts following formula

L(x，y，σ)＝G(x，y，σ)*f(x，y)

$G(x,y,\mathrm{\&sigma;})=\frac{1}{2\mathrm{\&pi;}{\mathrm{\&sigma;}}^2}{e}^{-\frac{(x^2+y^2)}{2{\mathrm{\&sigma;}}^2}}$

Wherein (σ) for metric space after the smoothing processing is the image of σ, (x, y σ) are Gaussian function to G to L, and (x y) is original image to f for x, y;

In second step, set up graphical rule space pyramid.Earlier original image is put and be twice, and with the image prototype of this image as Gauss's metric space pyramid first rank, the image prototype on later every rank is all obtained by the image prototype down-sampling of preceding single order, size is a preceding rank prototype

Adjacent two Gaussian image in every rank are made difference and are promptly obtained difference of Gaussian (DoG) pyramid in gaussian pyramid.Get the pyramid first rank ground floor graphical rule coordinate

Total exponent number of gold tower is log ₂(min (w, h))-2, wherein w is the original image width, h is the original image height;

In the 3rd step, with 2 * 9 adjacent pixels of the upper and lower layer of each pixel and same order in the image to be detected two width of cloth image, and own on every side 8 pixels compare, and look for extreme point, are defined as the candidate feature point;

The 4th goes on foot, and removes the unique point and the unsettled skirt response point of some low contrasts.The three-dimensional quadratic function of employing match comes the DoG functional value of accurate feature points and removes the unique point of low contrast.If the normalization of pixel point value is between [0,1] in the DoG image, can be with all

Point be judged to be the candidate extreme point of low contrast and filter out.Utilize the unique point at place, image border one bigger principal curvatures value to be arranged, but filter out at the low contrast features point of less this character of vertical direction curvature with edge at the peak value place and the intersect edge place of difference of Gaussian image;

In the 5th step, determine the unique point direction.For piece image f (x, y), pixel (x, y) mould value and the direction of locating gradient asked for as follows:

$m(x,y)=\sqrt{{(f(x+1,y)-f(x,y+1))}^2+{(f(x,y+1)-f(x,y-1))}^2}$

$\mathrm{\&theta;}(x,y)=\arctan \left(\frac{f(x,y+1)-f(x,y-1)}{f(x+1,y)-f(x-1,y)}\right)$

With the unique point sampling in the neighborhood window (neighborhood window size=3 * 1.5 * unique point yardstick) at center, and with the gradient direction of statistics with histogram neighborhood territory pixel.In gradient orientation histogram, when existing another to be equivalent to the peak value of main peak value 80% energy, then this direction is thought the auxilliary direction of this unique point;

The 6th step, generating feature point describing word.At first coordinate axis is rotated to be the direction of unique point, next be that 16 * 16 window is got at the center with the unique point, on per 4 * 4 fritter, calculate the gradient orientation histogram of 8 directions, obtain the accumulated value of each gradient direction, form a seed points, just can produce the proper vector of 128 dimensions like this for a unique point.Continue length normalization method again with proper vector;

The unique point operator that obtains like this is a kind of based on metric space, image zoom, rotation even affined transformation are maintained the invariance, have under the situation of complicated distortion at image, and the image local feature that can match a large amount of stable point is exactly described operator.

3. the target based on affine invariant point and optical flow computation according to claim 1 is discerned and tracking automatically, it is characterized in that the step of Feature Points Matching is as follows:

The first step, total m as the unique point of target image, the describing word array is (A ₁, A ₂..., A _m), total n of the unique point of image to be matched, the describing word array is (B ₁, B ₂..., B _n), to (A ₁, A ₂..., A _m) build the k-d tree, in the k-d tree, use BBF (Best-Bin-First) algorithm search B _j(j=1 ..., neighbour's unique point A n) _i(i=1 ..., m).As two unique point describing word A (a ₀, a ₁..., a ₁₂₇) and B (b ₀, b ₁..., b ₁₂₇) Euclidean distance is:

$d=\sqrt{\underset{i=0}{\overset{127}{\mathrm{\&Sigma;}}}{(a_i-b_i)}^2}$

When between the unique point describing word of two width of cloth images Euclidean distance d hour, these two unique points are exactly neighbour's unique point, they are called a pair of match point;

Second step, utilize RANSAC (RANdom SAmple Consensus) random sampling consistency algorithm to eliminate the mispairing unique point, step is:

(1) gets 4 characteristic matching at random to (A ₁, B ₁), (A ₂, B ₂), (A ₃, B ₃), (A ₄, B ₄), calculate corresponding homography matrix H

$H=\left[\begin{array}{ccc}{h}_{11}& h_{12}& h_{13}\\ h_{21}& h_{22}& h_{23}\\ h_{31}& h_{32}& h_{33}\end{array}\right]$

(2) unique point A _i(i=1 ..., 4) be C with the point after this matrix correspondence _iIf, A _iAnd C _iBetween Euclidean distance d change the operation of the 3rd step during less than error thresholds, otherwise change the operation of the 1st step;

(3) whether all possible characteristic matching is satisfied H to detection, all data are divided into " interior point " and " exterior point ";

(4) repeat above-mentioned 1-3 step operation N time;

(5) find out that to satisfy the characteristic matching that point is maximum in the corresponding matrix that each iterative computation goes out right, these points promptly are correct match points, and calculate final homography matrix H;

The unique point number of correct coupling is necessary for more than 4, can obtain homography matrix H, shows the Target Recognition success, otherwise gets next frame successively and target image carries out Target Recognition.

4. the target based on affine invariant point and optical flow computation according to claim 1 is discerned and tracking automatically, it is characterized in that the step of target following is as follows:

The first step, set up window W to be tracked by the affine invariant features point that Target Recognition obtains, calculate the gray scale difference quadratic sum SSD (Sum of Squared intensity Differences) of video image interframe, the moving characteristic window, repeat several steps, less than certain threshold value, the match is successful at this moment to think the characteristic window of two frames, promptly finds the position of character pair point in next frame up to s;

Second step, utilize RANSAC (RANdom SAmple Consensus) random sampling consistency algorithm, calculate the homography matrix H of next frame image

$H=\left[\begin{array}{ccc}{h}_{11}& h_{12}& h_{13}\\ h_{21}& h_{22}& h_{23}\\ h_{31}& h_{32}& h_{33}\end{array}\right]$

Can obtain H as last, think that then target following is successful, and eliminate the unique point that those do not meet homography matrix, enter again the target following of next frame; If can not obtain H, illustrate that target is followed to lose, carry out Target Recognition again.

Images