KR101885839B1 - System and Method for Key point Selecting for Object Tracking - Google Patents

Abstract

The present invention relates to an apparatus to select a feature point for object tracking, capable of performing robust object tracking, and a method thereof. According to the present invention, the apparatus to select a feature point for object tracking comprises: a video frame input unit to receive an image (It) of a current frame, an image (It+1) of a next frame, and a location of an object to be tracked; an object location tracking unit calculating movement of an i^th key point existing in an object at a time (t) to find the location of the object in the next frame; a forward and backward (FB) error value calculation unit to measure an error of a motion vector of the found key points in an FB error calculation type; a key point selection unit applying a weighted random sample consensus (W-RANDSAC) algorithm to remove outliers so as to select key points; and an object movement determination unit using a model of the selected key points to estimate movement of the object based on a least squares method.

Description

TECHNICAL FIELD [0001] The present invention relates to a feature point selection apparatus and method for object tracking,

The present invention relates to object tracking, and more particularly, to a feature point sorting device for object tracking, which enables robust object tracking by selecting reliable key points (inliers) by applying a weighted random sample consensus (W-RANSAC) ≪ / RTI >

Tracking video objects in the field of computer vision is a very important issue. In particular, keypoint-based object tracking methods have become the cornerstone of recent developments in various applications such as Advanced Driver System (ADAS) and intelligent surveillance system.

In the keypoint-based object tracking method, multiple keypoints are tracked in successive frames to predict the motion of the object, and the results are synthesized.

Therefore, in keypoint-based object tracking algorithm, it is important to remove outliers and select reliable keypoints.

To improve the speed and accuracy of keypoint-based tracking algorithms, it has been widely used to select and track keypoints that are generally good to track, such as corners or edges.

However, even when this method is applied, if the tracked object is overlapped by another object or the appearance changes, the possibility of tracking failure increases.

In order to solve this problem, there has been proposed a technique using an FB (Forward-Backward) error and a Median flow tracker that can measure an error of keypoint tracking in consideration of temporal continuity between frames.

In the median flow tracker, 50% of the FB error is determined as an ideal point, and the median of the remaining key points is determined to determine the motion of the object.

In order to improve the speed and accuracy of the keypoint-based tracking algorithm, it is generally necessary to detect keypoints in discontinuity such as a corner or an edge, track the points, Mean), there are the following problems.

The problem of the conventional method of tracking all the keypoints detected at the discontinuity point and using the average value is that the tracking performance is greatly degraded when the tracked object is overlapped by another object or the appearance changes.

In order to solve this problem, the proposed method is a median flow method in which the motion of detected minutiae points is tracked, and the motion of the object is tracked to median of the values.

However, since the intermediate value of the feature point motion does not represent the motion of the tracking object, the tracking performance is greatly degraded if the tracking object undergoes a change such as blocking.

Therefore, it is required to develop a new technique for solving the problem of the methods for object tracking.

Korean Patent Publication No. 10-2014-0141239 Korean Patent No. 10-1681104 Korean Patent No. 10-1234046

The object of the present invention is to solve the problem of the object tracking method of the related art, and it is an object of the present invention to provide a feature point selection device for object tracking for providing tracking improvement of a keypoint-based image- The purpose of the method is to provide.

The object of the present invention is to provide a feature point selection apparatus and method for tracking an object which can reliably track an object by selecting reliable key points by applying a weighted random sample consensus (W-RANSAC) algorithm .

The present invention employs a weighted random sample consensus (W-RANSAC) algorithm that exhibits excellent performance in eliminating anomalous points to select reliable key points and an error measurement method used to eliminate an anomalous point is an FB error The object of the present invention is to provide a feature point selection apparatus and method for tracking an object that can overcome the disadvantages of the key point based tracking method by using a Forward-Backward error calculation.

An object of the present invention is to provide a feature point selection apparatus and method for tracking an object that enables robust object tracking by estimating a geometric transformation possessed by a selected key point in a continuous frame by using a least squares method.

The objects of the present invention are not limited to the above-mentioned objects, and other objects not mentioned can be clearly understood by those skilled in the art from the following description.

를 입력받는 비디오프레임 입력부;시간 t에서의 객체 내부에 존재하는 i번째 키포인트의 움직임

을 구하여 다음 프레임에서의 객체의 위치

를 찾는 객체 위치 추적부;객체 위치 추적부에서 찾은 키포인트들의 모션 벡터의 에러를 FB 에러(Forward-Backward error) 계산 방식으로 측정하는 FB 에러값 계산부;W-RANSAC(weighted Random Sample Consensus)알고리즘을 적용하여 이상치(outlier)를 제거하여 키포인트들을 선별하는 키포인트 선별부;상기 키포인트 선별부에서 선별된 키포인트들의 모델을 이용하여 최소자승법을 적용하여 객체의 움직임

을 추정하는 객체 움직임 결정부;를 포함하는 것을 특징으로 한다.In order to accomplish the above object, according to the present invention, there is provided a feature point selection apparatus for tracking an object, comprising an image I _t of a current frame, an image I _{t +1} of a next frame,

A motion of an i-th key point existing in an object at a time t

The position of the object in the next frame

An FB error value calculation unit for measuring an error of a motion vector of key points found by the object position tracking unit by a forward error correction (FB) error calculation method, a weighted random sample consensus (W-RANSAC) A keypoint selection unit for selecting keypoints by removing outliers by applying a least squares method using a model of keypoints selected by the keypoint selection unit,

And an object motion determiner for estimating an object motion.

을,

또는

으로 정의하고, v_t는 모션벡터인 것을 특징으로 한다.Here, the motion of the i-th key point in the object at time t

of,

or

, And v _t is a motion vector.

으로 계산하고,

는 Euclidean distance를 이용하여 계산하고,

는

에서 t+1번째 프레임에서의 키포인트의 위치

를 추정한 후, 다시 역방향으로

에서 t번째 프레임에서의 키포인트의 위치

를 추정하여 구하는 것을 특징으로 한다.The FB error value calculation unit calculates the FB error value,

Lt; / RTI >

Is calculated using Euclidean distance,

The

The position of the key point in the (t + 1) th frame

, And then backward

The position of the key point in the tth frame

Is estimated.

In the key point selection unit, a weight for removing the outliers by applying a weighted random sample consensus (W-RANSAC)

으로 설정하고,

는 i번째 키포인트의 가중치,

는 i번째 키포인트의 FB 에러값,

는 FB 에러값의 평균이고, FB 에러가 작을수록 큰 가중치를 갖도록 하는 것을 특징으로 한다.

Respectively,

Is the weight of the i-th key point,

Is the FB error value of the i-th key point,

Is an average of the FB error values, and has a larger weight as the FB error is smaller.

를 입력받는 비디오프레임 입력 단계;시간 t에서의 객체 내부에 존재하는 i번째 키포인트의 움직임

을 구하여 다음 프레임에서의 객체의 위치

를 찾는 객체 위치 추적 단계;찾은 키포인트들의 모션 벡터의 에러를 FB 에러(Forward-Backward error) 계산 방식으로 측정하는 FB 에러값 계산 단계;W-RANSAC(weighted Random Sample Consensus)알고리즘을 적용하여 이상치(outlier)를 제거하여 키포인트들을 선별하는 키포인트 선별 단계;상기 선별된 키포인트들의 모델을 이용하여 최소자승법을 적용하여 객체의 움직임

을 추정하는 객체 움직임 결정 단계;를 포함하는 것을 특징으로 한다.According to another aspect of the present invention, there is provided a feature point selection method for tracking an object, comprising: extracting an image I _t of a current frame, an image I _{t +1} of a next frame,

A motion of an i-th key point existing in an object at a time t

The position of the object in the next frame

An FB error value calculation step of measuring an error of a motion vector of key points found by a forward-backward error calculation method, a weighted random sample consensus (W-RANSAC) A keypoint selection step of selecting keypoints by removing the keypoints from the keypoints, applying a least squares method using the selected keypoint models,

And an object motion determining step of estimating an object motion.

Here, the step of removing the outliers in the keypoint selection step may include calculating motion vectors of all the feature points, optionally selecting a subset of the motion vectors of the minimum feature points, ), Generating a model based on the generated model, and determining whether the generated model is consistent with all other data, and applying a selected subset and a weight value to select the most supported model .

The feature point selection apparatus and method for object tracking according to the present invention have the following effects.

First, tracking performance of keypoint-based image-based object tracking method can be improved in a single camera.

Second, robust object tracking is possible by selecting reliable keypoints (inliers) by applying the weighted random sample consensus (W-RANSAC) algorithm.

Third, the weighted random sample consensus (W-RANSAC) algorithm is applied to remove the anomalous points to select reliable keypoints, and the error measurement method used to remove the anomalies is the FB error We can overcome the disadvantages of the keypoint-based tracking method by using the forward-backward error calculation.

Fourth, the robust object tracking is enabled by estimating the geometric transformations of the selected keypoints in the successive frames using the least squares method.

Fifth, the error rate of keypoints is measured, and the keypoints are adaptively selected based on the measured error rate to improve the tracking performance, thereby increasing the applicability to a system for tracking objects in a single camera such as a surveillance system or a driver assistance system .

1 is a block diagram of a feature point selection apparatus for tracking an object according to the present invention
2 is a flowchart showing a method of selecting feature points for object tracking according to the present invention.
FIG. 3 is a block diagram showing the calculation of the FB error value (Forward-Backward error)
4 is a flowchart showing a method of removing outliers by applying the W-RANSAC algorithm
5 is a diagram showing an application example of a feature point selection method for object tracking according to the present invention

Hereinafter, a preferred embodiment of a feature point selection apparatus and method for object tracking according to the present invention will be described in detail as follows.

The features and advantages of the feature point selection apparatus and method for object tracking according to the present invention will be apparent from the following detailed description of each embodiment.

1 is a block diagram of a feature point selection apparatus for tracking an object according to the present invention.

The present invention employs a weighted random sample consensus (W-RANSAC) algorithm, which shows excellent performance in eliminating an anomaly point, to select reliable keypoints, and an error measurement method used to remove an anomaly point is an FB error Value-based (Forward-Backward error) calculation to overcome the disadvantages of the keypoint-based tracking method.

The present invention includes a configuration for making robust object tracking possible by estimating the geometric transformation that the selected keypoints have in successive frames using a least squares method.

를 입력받는 비디오프레임 입력부(10)와, 시간 t에서의 객체 내부에 존재하는 i번째 키포인트의 움직임

을 구하여 다음 프레임에서의 객체의 위치

를 찾는 객체 위치 추적부(20)와, 객체 위치 추적부(20)에서 찾은 키포인트들의 모션 벡터의 에러를 FB 에러(Forward-Backward error) 계산 방식으로 측정하는 FB 에러값 계산부(30)와, 확률적 이상치 제거 방법(outlier detecrtion method)인 RANSAC에 가중치로서 활용하도록 하는 W-RANSAC 알고리즘을 적용하여 이상치(outlier)를 효과적으로 제거하고 신뢰할 수 있는 키포인트들을 선별하는 키포인트 선별부(40)와, 선별된 키포인트들의 모델을 이용하여 최소자승법을 적용하여 객체의 움직임

를 추정하는 객체 움직임 결정부(50)를 포함한다.As shown in FIG. 1, the feature point selection apparatus for tracking an object according to the present invention includes an image I _t of a current frame, an image I _{t +1} of a next frame,

(I) a video frame input unit 10 for inputting a motion of an i-th key point existing in the object at time t,

The position of the object in the next frame

An FB error value calculation unit 30 for measuring an error of a motion vector of key points found by the object position tracking unit 20 by a forward error correction (FB) error calculation method, A key point sorting unit 40 for effectively removing outliers and selecting reliable key points by applying a W-RANSAC algorithm to be used as a weight to RANSAC, which is an outlier detecration method, By applying the least squares method using the keypoint model,

And an object motion determiner 50 for estimating an object motion.

A feature point selection method for object tracking according to the present invention will now be described.

FIG. 2 is a flowchart illustrating a feature point selection method for object tracking according to the present invention.

The feature point selection method for object tracking according to the present invention includes a video frame input step S201, a key point based tracking step S202, an FB error value calculation step S203, a reliable key point selection Step S204, and step S205 of determining object motion.

The feature point selection method for object tracking according to the present invention will be described in detail as follows.

를 입력받고, 다음 프레임에서의 객체의 위치

를 찾는 과정이다.The object tracking consists of the image I _t of the current frame, the image I _{t +1} of the next frame,

And the position of the object in the next frame

.

은 수학식 1 또는 수학식 2에서와 같은 관계가 성립한다.Movement of the i-th keypoint inside the object at time t

Has the same relationship as in Equation (1) or Equation (2).

Here, v _t is generally referred to as a motion vector.

In general, a keypoint-based object tracking method detects an edge or a corner point, and tracks motion vectors of the points in an optical flow manner to determine a motion of an object by taking an average value or a median value.

However, some of the motion vectors of the keypoints found in this way do not reflect the movement of the object actually tracked by various noises.

In order to solve such a problem, in the present invention, the error of the motion vector is measured by the Forward-Backward (FB) error method and the motion of the object to be tracked is estimated using the reliable motion vectors.

3 is a block diagram showing the concept of a calculation of an FB error value (forward-backward error).

The formula for obtaining the FB error is as shown in Equation 3 below.

는

에서 t+1번째 프레임에서의 키포인트의 위치

를 추정한 후, 다시 역방향으로

에서 t번째 프레임에서의 키포인트의 위치

를 추정함으로써 구할 수 있다.here

The

The position of the key point in the (t + 1) th frame

, And then backward

The position of the key point in the tth frame

Can be obtained.

That is, the FB error is small when tracking the keypoint in the forward direction and then tracking backward in the backward direction at the same key point.

는 Euclidean distance를 이용하여 계산할 수 있다.Also

Can be calculated using the Euclidean distance.

Therefore, the smaller the FB error value, the better the feature point.

Applying the W-RANSAC algorithm, which uses the measured error as a weight to RANSAC, which is a generally superior outlier detecrtion method, effectively removes outliers and provides reliable keypoints Can be sorted out.

At this time, the weight for W-RANSAC is set as shown in Equation (4).

는 i번째 키포인트의 가중치,

는 i번째 키포인트의 FB 에러값,

는 FB 에러값으 평균이고,here,

Is the weight of the i-th key point,

Is the FB error value of the i-th key point,

0.0 > FB < / RTI > error value,

In this way, the smaller the FB error, the larger the weight, and the greater the contribution to the model that is finally found.

The goals of the W-RANSAC model applied in the object tracking method according to the present invention are as follows.

An object is a set of feature points, and the movement of an object can be seen as a movement of a set of points.

However, due to problems such as noise, the points within an object do not represent the same movement.

Therefore, it is a problem to solve by estimating a subset of points with the same moving component (or motion vector) as reliable keypoints.

The W-RANSAC process to solve this problem is as follows.

4 is a flowchart illustrating a method of removing an outlier by applying the W-RANSAC algorithm.

First, motion vectors of all feature points are calculated (S401)

Subsequently, the motion vectors of the minimum feature points are arbitrarily selected as a subset (S402), and the selected subset is assumed to be an inlier, and a model is generated based on the selected subset.

In step S404, it is determined whether or not the generated model matches all the other data. In step S404, the model having the most support is selected by applying the selected subset and the weight value.

를 추정할 수 있다.Finally, applying the least-squares method using the best-fit subset, ie, a model of keypoints,

Can be estimated.

The apparatus and method for selecting feature points for object tracking according to the present invention as described above selects trusted keypoints by applying a weighted random sample consensus algorithm (W-RANSAC) The error measurement method used to remove anomalies uses the FB error value (Forward-Backward error) calculation and estimates the geometric transformation of the selected keypoints in successive frames using the least squares method. .

5 is a block diagram showing an application example of a feature point selection method for object tracking according to the present invention.

The feature point selection apparatus and method for object tracking according to the present invention measures the error rate of keypoints and adaptively selects keypoints based on the measured error rate to improve the tracking performance, It is more applicable to systems that track objects in a single camera.

As described above, it will be understood that the present invention is implemented in a modified form without departing from the essential characteristics of the present invention.

It is therefore to be understood that the specified embodiments are to be considered in an illustrative rather than a restrictive sense and that the scope of the invention is indicated by the appended claims rather than by the foregoing description and that all such differences falling within the scope of equivalents thereof are intended to be embraced therein It should be interpreted.

10. Video frame input unit 20. Object position tracking unit
30. FB error value calculation unit 40. Key point selection unit
50. Object motion determination unit

Claims (9)

The image I _t of the current frame, the image I _{t + 1} of the next frame, and the position of the tracked object

A video frame input unit receiving the input video frame;
Movement of the i-th keypoint inside the object at time t

The position of the object in the next frame

An object position locator for finding an object;
An FB error value calculation unit for measuring an error of a motion vector of key points found by the object position tracking unit by a forward error correction (FB) error calculation method;
A key point selection unit for applying a weighted random sample consensus (W-RANSAC) algorithm to remove outliers to select key points;
The key point selection unit selects the keypoints using the least squares method to determine the motion of the object

And an object motion determiner for estimating an object motion,
In the key point selection unit, a weight for removing an outlier is applied by applying a weighted random sample consensus (W-RANSAC)

Respectively,

Is the weight of the i-th key point,

Is the FB error value of the i-th key point,

Is an average of the FB error values, and has a larger weight as the FB error is smaller. 2. The method according to claim 1, wherein the motion of the i-th key point existing within the object at time t

of,

or

, And v _t is a motion vector. 2. The method as claimed in claim 1, wherein the FB error value calculation unit

Lt; / RTI >

Is calculated using Euclidean distance,

The

The position of the key point in the (t + 1) th frame

, And then backward

The position of the key point in the tth frame

Wherein the feature point discrimination device for estimating the feature points comprises: delete The image I _t of the current frame, the image I _{t + 1} of the next frame, and the position of the tracked object

A video frame input step of inputting a video frame;
Movement of the i-th keypoint inside the object at time t

The position of the object in the next frame

An object position tracking step of searching for an object;
An FB error value calculation step of measuring errors of the motion vectors of the found keypoints by a forward error correction (FB) error calculation method;
A keypoint selection step of applying a weighted random sample consensus (W-RANSAC) algorithm to remove outliers to select keypoints;
By applying the least squares method using the model of the selected key points,

And an object motion determining step of estimating an object motion,
In the keypoint selection step, a weight for removing the outliers by applying a weighted random sample consensus (W-RANSAC)

Respectively,

Is the weight of the i-th key point,

Is the FB error value of the i-th key point,

Is an average of the FB error values, and has a larger weight as the FB error is smaller. 6. The method according to claim 5, wherein, in the object position tracking step, the motion of the i-th key point existing in the object at time t

of,

or

, And v _t is a motion vector. 6. The method of claim 5, wherein the calculating of the FB error value comprises:

Lt; / RTI >

Is calculated using Euclidean distance,

The

The position of the key point in the (t + 1) th frame

, And then backward

The position of the key point in the tth frame

And estimating a feature point of the object. delete 6. The method of claim 5, wherein removing the outlier in the keypoint selection step comprises:
Calculating motion vectors of all feature points,
Selecting a subset of the motion vectors of the minimum feature points, generating a model based on the selected subset as a key point,
Determining whether the generated model is consistent with all other data, and selecting a model with the most support by applying a selected subset and a weight value.

Images