JP2001060265A - Device and method for image processing and medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To improve the precision of feature tracing. SOLUTION: A feature point extraction part 3 extracts feature points from an object image to be traced on the basis of inputted image data and a reference pattern setting part 5 sets the plural extracted feature points as a reference pattern. A normalized pattern matching part 7 performs a pattern matching process in a search area set by a search area setting part 4 by using the reference pattern set by the reference pattern setting part 5. A score value decision means 9 decides whether or not the score value of the matching is larger than a threshold and instructs the search area setting part 4 to set a search area again when deciding that the score value is less than the threshold and a tracing result output part 8 to output the tracing result when deciding that the score value is larger than the threshold. Further, the score value decision part 9 instructs a reference pattern update part 10 to update the reference pattern according to specific conditions.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image processing apparatus, method, and medium, and more particularly, to determining a search area and updating a search pattern when performing template matching, and correcting a tracked feature point motion trajectory. Also, the present invention relates to an image processing apparatus and method for performing feature tracking with high accuracy, and a medium.

[0002]

2. Description of the Related Art In order to extract and analyze the movement of a moving object,
Changes in features (position, shape, brightness, etc.) such as textures, points, lines, and planes (areas) in the images between the preceding and following frames from the observed time-series images based on the frame of the predetermined image It is necessary to perform processing of detecting the same and tracking them so as to make the same one correspond. This is commonly called "feature tracking."

[0003] The feature tracking methods can be broadly classified into three methods, that is, a contour feature tracking method, a line feature tracking method, and a point feature tracking method, depending on a moving object and an analysis purpose. The contour feature tracking method
It is mainly used for tracking a flexible object (non-rigid object) whose shape is deformed, and the line feature tracking method and the point feature tracking method are often used for tracking a rigid body whose shape is not deformed.

Here, a commonly used point feature tracking method will be described with reference to FIG. As shown in FIG. 1, in a predetermined time-series image, an image at time t is F (i, j), and an image at time t + 1 is G
(I, j). Also, the coordinates of the feature point in the image F (i, j) are set to (Xt, Yt), and the coordinates (Xt, Y
Let T (i, j) be a template (existing pattern model) centered on t).

When time elapses from time t to time t + 1, and coordinates of feature points of image G (i, j) when image F (i, j) moves to the position of image G (i, j) (Xt
+1, Yt + 1) is calculated (tracked) by calculating the distance between the pattern model T (i, j) and
The shortest distance method by finding the position of the pattern model that minimizes the distance, the template matching method by sequentially updating the template being tracked for each frame, SSDA (Sequential Similarity Detection Algorith
m) method, a correlation method for extracting the position where the correlation value in the search area is maximum, a similarity method (a normalized correlation method) for finding the position where the angle between the known pattern vector and the pattern vector in the search area is minimum, Image F (i, j) and image G (i, j
There is a transposition vector tracking method for directly obtaining a movement vector during j).

[0006]

In any of the above-mentioned methods, there is a problem that it is difficult to set a search area. In other words, when the search area is set small, the processing speed increases and the probability of erroneous detection decreases, but it becomes impossible to track a moving object with a large movement amount. Conversely, when the search area is set large, the movement amount Although it is possible to track a moving object with a large size, if there are similar patterns around it, erroneous detection may occur and the processing speed will be slow, making it difficult to set an appropriate search area. Was.

Another problem is that it is not easy to track a moving object due to a change in pattern shape. That is, by the rotation of the motion object or the change of the camera viewpoint,
There is a possibility that the shape of the observed pattern and the shape of the known pattern may be significantly different, and there is a problem that the tracking of the moving object may not be performed due to a decrease in the matching score or occurrence of error matching.

[0008] Further, since the tracking result is greatly affected by the shape and the motion situation of the object, and the change of the environmental light in the field, the viewpoint of the object greatly changes.
In general, there has been a problem that it is not easy to accurately track feature points.

The present invention has been made in view of such circumstances. When performing template matching, a search area is determined, a search pattern is updated, and a tracked feature point motion trajectory is also corrected. Accordingly, an object of the present invention is to enable reliable feature point tracking.

[0010]

According to the present invention, an image processing apparatus is defined by using input means for inputting an image and differential image information for each pixel of the image input by the input means. Extracting means for obtaining eigenvalues of the feature amount matrix and extracting points whose eigenvalues are equal to or more than a threshold value as feature points; and setting means for setting a predetermined number of pixels including the feature points extracted by the extracting means as a reference pattern. Calculating means for calculating the degree of similarity with the reference pattern set by the setting means in a predetermined area of the image, and searching for the area in which the degree of similarity calculated by the calculating means is equal to or more than a predetermined value, over a plurality of images. And a tracking means for tracking a predetermined subject in the image.

The calculating means uses a normalized correlation method,
The degree of similarity can be calculated.

[0012] The tracking means may use a multidimensional function curve obtained by using a least squares method as a tracking result based on a search result over a plurality of images.

According to a fourth aspect of the present invention, there is provided an image processing method comprising: an input step of inputting an image; and a feature amount matrix defined using differential image information for each pixel of the image input in the input step. An extraction step of obtaining a characteristic value and extracting a point whose characteristic value is equal to or larger than a threshold value as a feature point; a setting step of setting a predetermined number of pixels including the characteristic point extracted in the process of the extraction step as a reference pattern; Calculating a similarity between the reference pattern set in the setting step and the similarity calculated in the setting step in a predetermined area, and setting the area in which the similarity calculated in the calculation step is equal to or more than a predetermined value over a plurality of images. A tracking step of tracking a predetermined subject in the image by searching.

According to a fifth aspect of the present invention, a program for a medium obtains an eigenvalue of a feature amount matrix defined using differential image information for each pixel of an input image, and determines that the eigenvalue is equal to or larger than a threshold value. An extraction step for extracting as a feature point;
A setting step of setting a predetermined number of pixels including the feature points extracted in the processing of the extraction step as a reference pattern,
A calculating step of calculating a similarity with the reference pattern set in the processing of the setting step in a predetermined area of the image; and an area in which the similarity calculated in the processing of the calculating step is equal to or more than a predetermined value, the plurality of images By exploring over
And a tracking step of tracking a predetermined subject in the image.

According to a sixth aspect of the present invention, there is provided an image processing apparatus comprising: an input unit for inputting an image; an extracting unit for extracting a feature point from the image input by the input unit; and a predetermined unit including the feature point extracted by the extracting unit. Setting means for setting the number of pixels as a reference pattern, search area setting means for setting a search area of a predetermined size in the image, and setting by the setting means within the search area set by the search area setting means. Calculating means for calculating the similarity with the reference pattern, determining means for determining whether the similarity calculated by the calculating means is greater than a predetermined value, and determining that the similarity is greater than the predetermined value by the determining means If not, resetting means for resetting the search area, and searching for the area where the similarity is determined to be greater than the predetermined value by the determining means, over a plurality of images. Tracking means for tracking a predetermined subject of an image, wherein the processing of the calculating means, the determining means, and the resetting means is performed until the similarity is determined to be larger than the predetermined value or set by the resetting means. Search area
The process is repeated until it is determined that the region is larger than a region of a predetermined size.

According to a ninth aspect of the present invention, in the image processing method, an input step of inputting an image, an extraction step of extracting a feature point from the image input in the processing of the input step, and a feature extracted in the processing of the extraction step. A setting step of setting a predetermined number of pixels including points as a reference pattern, a search area setting step of setting a search area of a predetermined size in an image, and a search area set in the processing of the search area setting step. A calculating step of calculating a similarity with the reference pattern set in the processing of the setting step; a determining step of determining whether the similarity calculated in the processing of the calculating step is greater than a predetermined value; If the similarity is not determined to be greater than the predetermined value in the processing of step (a), the similarity is determined to be smaller than the predetermined value in the processing of the resetting step of resetting the search area and the determination step. An area when it is determined to be larger,
A tracking step of tracking a predetermined subject of the image by searching over a plurality of images, the processing of the calculating step, the determining step, and the resetting step being performed until the similarity is determined to be larger than the predetermined value. Alternatively, the search area is repeatedly performed until it is determined that the search area set in the processing of the resetting step is larger than an area having a predetermined size.

[0017] The program of the medium according to claim 10 is:
An extraction step of extracting feature points from an image, a setting step of setting a predetermined number of pixels including the feature points extracted in the processing of the extraction step as a reference pattern, and setting a search area of a predetermined size in the image A search area setting step, a calculation step of calculating a degree of similarity with the reference pattern set in the processing of the setting step in the search area set in the processing of the search area setting step, and a calculation step of calculating the similarity. A determining step of determining whether the similarity is greater than a predetermined value; a resetting step of resetting the search area if the similarity is not determined to be greater than the predetermined value in the processing of the determining step; By searching a plurality of images for an area in which the similarity is determined to be larger than the predetermined value in the processing of (1), tracking of a predetermined subject in the image is performed. The processing of the calculating step, the determining step, and the resetting step is performed until the similarity is determined to be larger than the predetermined value, or the search area set in the processing of the resetting step has a predetermined size. It is repeatedly performed until it is determined that the area is larger than the area.

An image processing apparatus according to claim 11, wherein the input means inputs an image, the extracting means extracts feature points from the image input by the input means, and the predetermined means includes the feature points extracted by the extracting means. Setting means for setting the number of pixels as a reference pattern, calculating means for calculating a similarity with the reference pattern set by the setting means in a predetermined area in the image, and similarity calculated by the calculating means. Determining means for determining whether or not the similarity is greater than a predetermined value; and determining that the similarity is not greater than the predetermined value by the determining means.
A resetting means for resetting the reference pattern; and a tracking means for tracking a predetermined subject of the image by searching over a plurality of images for an area when the similarity is determined to be larger than the predetermined value by the determining means. Calculating means,
The processing of the determining means and the resetting means is repeatedly performed until it is determined that the similarity is larger than a predetermined value.

According to a fourteenth aspect of the present invention, in the image processing method, an input step of inputting an image, an extraction step of extracting a feature point from the image input in the processing of the input step, and a feature extracted in the processing of the extraction step. A setting step of setting a predetermined number of pixels including points as a reference pattern, a calculation step of calculating a similarity with the reference pattern set in the processing of the setting step in a predetermined area in the image, A judging step of judging whether or not the similarity calculated in the processing is larger than a predetermined value, and if the similarity is not judged to be larger than the predetermined value in the processing of the judging step,
A tracking step of tracking a predetermined subject in an image by searching a plurality of images for an area when the similarity is determined to be larger than a predetermined value in the processing of the resetting step of resetting the reference pattern and the determination step And the steps of the calculating step, the determining step, and the resetting step are repeatedly performed until it is determined that the similarity is greater than a predetermined value.

[0020] The program of the medium according to claim 15 is:
An extraction step of extracting feature points from the input image;
A setting step of setting a predetermined number of pixels including the feature points extracted in the processing of the extraction step as a reference pattern,
A calculating step of calculating a similarity with the reference pattern set in the processing of the setting step within a predetermined area in the image;
A determining step of determining whether or not the similarity calculated in the processing of the calculating step is larger than a predetermined value; and resetting the reference pattern if the similarity is not determined to be larger than the predetermined value in the processing of the determining step. A resetting step, and a tracking step of tracking a predetermined subject in the image by searching a plurality of images for an area when the similarity is determined to be greater than the predetermined value in the processing of the determining step. The processing of the step, the determining step, and the resetting step is repeatedly performed until it is determined that the similarity is greater than a predetermined value.

An image processing apparatus according to claim 1, wherein
In the image processing method described in the above, the eigenvalue of the feature amount matrix defined using the differential image information is obtained for each pixel of the input image, and the eigenvalue is equal to or larger than the threshold value Is extracted as a feature point, a predetermined number of pixels including the extracted feature point are set as a reference pattern, a similarity with the reference pattern is calculated in a predetermined area of the image, and the similarity is determined by a predetermined value. A predetermined subject in the image is tracked by searching a plurality of images for an area that is equal to or larger than the value.

An image processing apparatus according to claim 6,
In the image processing method described in the above, and the medium described in the claim 10, feature points are extracted from the input image, a predetermined number of pixels including the extracted feature points are set as a reference pattern, A search area of a predetermined size is set, and the similarity with the reference pattern is calculated in the search area. If the similarity is not determined to be larger than the predetermined value, the search area is reset and the similarity is calculated. By searching a plurality of images for a region determined to be larger than the predetermined value, a predetermined subject of the image is tracked, and until the similarity is determined to be larger than the predetermined value, or a reset search is performed. Until it is determined that the area is larger than the area of the predetermined size, the calculation of the similarity and the comparison with the predetermined value are repeatedly performed.

In the image processing apparatus according to the eleventh aspect, the image processing method according to the fourteenth aspect, and the medium according to the fifteenth aspect, feature points are extracted from the input image, and the extracted feature points are extracted. Is set as a reference pattern, the similarity to the reference pattern is calculated in a predetermined area in the image, and if the similarity is not determined to be larger than the predetermined value, the reference pattern is re-created. Is set,
The area when the similarity is determined to be larger than the predetermined value is
By searching over a plurality of images, a predetermined subject of the image is tracked, and resetting of the reference pattern and calculation of the similarity are repeatedly performed until it is determined that the similarity is larger than the predetermined value.

[0024]

FIG. 2 is a diagram showing the internal configuration of an image processing apparatus 1 to which the present invention is applied. Image data of a time-series image to be processed is input to the image input unit 2. The image data input to the image input unit 2 is output to the feature point extraction unit 3 and the search area setting unit 4. The feature point extraction unit 3 extracts feature points based on the input image data (details will be described later), and outputs the feature points to the reference pattern setting unit 5. The reference pattern setting unit 5 creates a reference pattern from the input feature points, and outputs the reference pattern to the terminal A of the switch 6.

The search area setting section 4 sets a search area,
The data relating to the set search area and the image input unit 2
Is output to the normalized pattern matching unit 7. The normalized pattern matching unit 7
Using the reference pattern input via the switch 6,
A pattern matching process is performed in the search area set by the search area setting unit 4, and the result is output to the tracking result output unit 8 and the score value determination unit 9.

The score value judging section 9 holds a predetermined value (threshold), and the score value obtained by pattern matching is
It is determined whether or not it is equal to or greater than the threshold. The reference pattern updating unit 10 updates the reference pattern based on the determination by the score value determining unit 9 and outputs the updated reference pattern to the terminal B of the switch 6. Also,
When determining that the score value is equal to or less than the threshold, the score value determining unit 9 instructs the search area setting unit 4 to reset the search area, and when determining that the score value is equal to or greater than the threshold, the tracking result output unit. 8 is input to the tracking result processing unit 11
To output to.

The tracking result processing section 11 performs processing such as calculating the coefficient of the n-th order curve using the input data to ensure the tracking information of the subject to be tracked.

Next, with reference to the flowchart of FIG. 3, the feature point extraction processing by the feature point extraction unit 3 will be described. In step S <b> 1, image data of an image f (x, y) is input from the image input unit 2 to the feature point extraction unit 3. The feature point extracting unit 3 determines in step S2 that the image f
The rate of change of (x, y) in the x direction and the rate of change in the y direction are calculated by the following equations (1) and (2), respectively.

F′x (x, y) = ∂f (x, y) / ∂x (1) f′y (x, y) = ∂f (x, y) / ∂y ... (2) In step S3, each pixel P based on the image change rate in a window composed of a predetermined number of pixels (w × w)
The coefficient of the feature amount matrix R (x, y) of (x, y) is calculated according to the following equation (3). In step S3, the pixel P (x, y) to be processed is, for example, a pixel located at the center of the image window.

[0030]

(Equation 1)

In step S4, eigenvalues λ1 and λ2 are obtained by diagonalizing the feature matrix R (x, y) obtained in step S3. The obtained eigenvalue λ1,
The smaller one of λ2 is set as the feature value λ. In step S5, the characteristic value λ is set to a predetermined threshold λ
It is determined whether it is greater than t. The determination in step S5 is a process for defining a traceable feature point pattern. If it is determined in step S5 that the characteristic value λ is larger than the threshold value λt, the process proceeds to step S6.

In step S6, the pixel P (x, y) to be processed is set as a feature point, and the flow advances to step S8. On the other hand, in step S5, the characteristic value λ
Is determined to be smaller than the threshold λt,
Go to 7. In step S7, the pixel P (x, y) to be processed is not set as a feature point, and the process proceeds to step S8. In step S8, the input image f
It is determined whether or not the above-described calculation has been completed for all pixels in (x, y).

If it is determined in step S8 that the calculation has not been completed for all the pixels, step S3
Then, the subsequent processing is repeated, and when it is determined that the calculation for all the pixels is completed, the process proceeds to step S9 (FIG. 4). Before describing the processing after step S9,
The processing up to step S8 will be further described with reference to FIG.

FIG. 5A shows an image f input to the feature point extraction unit 3 via the image input unit 2 in step S1.
(X, y). In FIG. 5, as a window having a predetermined number of pixels, 5 × 5 25 pixels (therefore, 1 pixel)
The description will be made by taking an image window composed of (a square represents one pixel) as an example. FIG. 5B shows a calculation result when the change rate of the input image f (x, y) in the x direction is calculated in step S2. Similarly, FIG.
(C) shows a calculation result when the change rate in the y direction is calculated.

FIG. 5D shows the calculated change rate based on the calculated change rate.
In step S3, a calculation result when the coefficient of the feature amount matrix is calculated according to equation (3) is shown. FIG.
(E) shows the eigenvalues λ1 and λ2 calculated in step S4.
Is shown. Further, FIG. 5F shows the value set as the characteristic value λ in step S5.

From the results shown in FIG. 5, an image window including straight lines and edges (four left diagrams in FIG. 5) is not selected as an image window including a feature point because the feature value λ is 0 (not appropriate). ) Is determined. On the other hand, in the image window including the corners (the two figures on the right in the figure), if the fixed value λ is 3 and the threshold value λt is set as a numerical value of 3 or less, the image window including the feature points (hereinafter, referred to as “the window”) Where appropriate, described as a feature window).

As described above, the reason why an image window including a straight line or an edge is not used as a feature window is that when feature tracking by pattern matching is performed in subsequent processing, it may cause mismatching. . Conversely, when a feature window is set by the processing described above, an image window including a corner is set as a feature window (candidate).
Can be confirmed.

Returning to the description of the flowchart of FIG. 4, the feature point extracting unit 3 determines in step S9 that the feature point P (x,
The feature values λ corresponding to the plurality of points indicated by y) are rearranged in descending order. In step S10, the feature windows centered on the feature point P (x, y) are searched in order from the largest feature value λ rearranged in the descending order to determine whether there is an overlapping feature window. Using the search result, in step S11, it is determined whether or not there is an overlapping feature window. If it is determined that there is no overlapping feature window, the process proceeds to step S12. If it is determined that there is an overlapping feature window, Proceed to step S13.

In step S12, the characteristic point P
A feature window centered at (x, y) is created, and no feature window is created in step S13. It is determined in step S14 whether or not such processing has been performed on all feature points. If it is determined that the check of all feature points has not been completed, the process returns to step S10, and the subsequent processing is performed. If it is determined that all the feature points have been checked, the feature point extraction (feature window setting) process is terminated.

The image f of the frame in the time-series image
(X, y, t) (where t represents time, and the image of the first frame serving as a reference is assumed to be t = 1), the image including the corner and the like obtained by the above-described processing. Is stored in the reference pattern setting unit 5 as a reference pattern (template) Ti1 (x, y) (i = 1 to P)
To be stored. Also, their center point (ie,
Here, the feature point) is described as Pi1 (xi1, yi1),
This coordinate value is also stored in the reference pattern setting unit 5.

Time-series image f (x, y, t) (time t>
In order to track the movement of the pattern Tit (x, y) of the feature window centering on the feature point Pit (xit, yit) using 1), a pattern matching method using normalized correlation is used. However, it is not easy to set a search area for actually tracking the target efficiently due to changes in the speed, direction, and the like of the target. In other words, if the search area is set to be small, the processing time for tracking becomes faster, which is advantageous for suppressing erroneous tracking caused by a similar pattern around it. Come. Conversely, if the search area is set to be large, it is possible to track even an object with a fast moving speed, but the time required for the tracking process becomes longer, and problems such as occurrence of erroneous tracking due to similar patterns in the surroundings occur. Therefore, it is necessary to set a search area that can flexibly respond to the speed of the motion target.

Therefore, in the present embodiment, the score value of the pattern matching based on the normalized correlation is used as an evaluation criterion, and the search area is appropriately updated, thereby flexibly responding to the speed of the moving object. Tracking. Specifically, a method of setting a search area and setting a reference pattern used for pattern matching will be described with reference to the flowchart of FIG. Step S
At 31, a time-series image f (x, y, t) (t = 1 to F) is input from the image input unit 2 to the search area setting unit 4. In step S32, the characteristic window is set as described with reference to the flowcharts of FIGS. The set feature window (the feature window stored in the reference pattern setting 5) is set as the initial feature pattern T _i1 .

In step S3, the search area setting unit 4
Sets the time t to the time t + 1 and sets the recursive mode flag T Cont
Enable inue. By setting the time t to the time t + 1, the processing target image becomes f (x, y, t + 1).
In step S34, the search area setting unit 4 performs initial setting of the search area. As the search area to be initially set, for example, the size is set to w × w (the same size as the feature window), and the center coordinates are (X _ik + DX _ik , Y _ik + D)
Y _ik ). The normalized pattern matching unit 7
In step S34, when the search area set by the search area setting unit 4 is stored in the reference pattern setting unit 5 and input via the switch 6, pattern matching processing is performed using the reference pattern Ti1.

The score value determination unit 9, in step S36, the matching degree by normalizing the pattern matching section 7 (score value), whether the thresholds T ₁ is greater than that has been set in advance. The threshold value T _1, for example,
80 (%) is set. In step S36, if the score value is determined to be greater than the threshold value T _1, the process proceeds to step S42, whether the time t is greater than time F of the last frame, in other words, the image f (x to be processed,
It is determined whether or not y, t) remains. Step S
If it is determined at 42 that the time t is smaller than the time F of the last frame, the process returns to step S33, and the subsequent processing is repeated.

On the other hand, if in step S36, it is determined as the score value is smaller than the threshold value T _1, step S
Proceed to 37. The score value determining unit 9 is also supplied with data on the search area in addition to the score value from the normalized pattern matching unit 7, and uses the data to execute step S37.
Is performed. That is, the score value determination unit 9 in step S37, the search area is determined or smaller or not than the threshold value T ₂ which is set in advance. This step S3
The process of 7 may be performed by the search area setting unit 4 by giving an instruction to the search area setting unit 4 by the score value determining unit 9, but here, it is assumed that the score value determining unit 9 performs the processing. I do.

In the present embodiment, the search area is also updated appropriately, but the observation image (the image to be processed)
In the case where the influence of the noise in is large, it is assumed that the feature pattern cannot be tracked. Therefore, it is necessary to set the maximum value of the search area. Therefore, for example, the maximum value (threshold value T ₂ ) of the search area is calculated by (W + 5DXik) ×
(W + 5DYik) is set.

[0047] In step S37, the score value determination unit 9 is, if the search area is determined to be smaller than the threshold value T _2, the instruction for resetting the search area to the search area setting unit 4 is issued, at step S37, the search The area setting unit 4 resets the search area to a large value. Then, the processing from step S35 is repeated using the updated search area.

Meanwhile, if in step S37, it is determined the search area is larger than the threshold value T _2, step S
Proceed to 39. In step S39, the reference pattern updating unit 10 sets the feature pattern in the image one frame before as a new reference pattern Ti (t-1) (x, y), and via the switch 6, the normalized pattern matching unit 7 Output to Then, in step S40, it is determined whether or not the recursive mode flag T Continue is valid. If it is determined that the recursive mode flag T Continue is valid, the process proceeds to step S41, the recursive mode flag T Continue is set to invalid, and the process returns to step S34. , And the subsequent processes are repeated.

On the other hand, if it is determined in step S40 that the recursive mode flag T Continue is not valid,
Proceeding to step S42, it is determined whether or not the time t is greater than the time F of the last frame. If it is determined that the time t is greater, the process returns to step S33, and the subsequent processing is repeated to determine that the time is not greater. That is, when it is determined that there is no image to be processed, the processing of this flowchart ends. When this flowchart ends, the score value determination unit 9 outputs a permission signal to the tracking result output unit 8 to output the obtained tracking result to the tracking result processing unit 11.

The setting of the search area and the reference pattern described with reference to the flowchart of FIG. 6 will be further described with reference to FIGS. 7 and 8. FIG. 7 is a diagram illustrating how to set a search area (the processing of steps S34 to S38). The reference pattern serving as a reference in the image f (x, y, k) of the k-th frame is represented by Tik (x, y) (i = 1,
, P), the center coordinate value of the reference pattern in the image f (x, y, k) is (Xik, Yik), and (k−
1) The moving distance of the reference pattern from the frame to the k-th frame is (DXik, DYik). (K + 1)
In order to track the reference pattern in the image f (x, y, k + 1) of the frame, the size is set to w × w and the center coordinate is set to (Xik + DXik, Y) as the initial value of the search area.
ik + DYik) (step S34).

Then, the reference pattern Tit (x, y)
Using (i = 1,..., P, t <k), pattern matching within the set search area (processing in step S35)
If the conducted, less than faction value T ₁ that the score value is prepared (in step S36), expanding the search area in the XY direction (process of step S37, S38), again, the newly set search area Perform pattern matching within.
When the score value of the pattern matching is larger than the clique value T ₁ that is prepared, the tracking process is completed.

[0052] region 1 (where the initial search area) when tracking the motion object by pattern matching in, since the score value is smaller than the threshold value T _1, the search area is expanded to the region 2, is performed tracked again . Even in the area 2, the moving object cannot be tracked (the score value is smaller than the threshold value T ₁ ), and thus such an operation is repeated to expand the search area to the area 3. When the area is enlarged to the area 3, the moving object is tracked, and the processing is completed.

FIG. 8 shows the updating of the reference pattern (step S
FIG. 39 is a diagram illustrating the process (39). Generally, the score value of template matching using normalized correlation becomes smaller due to the movement posture of the tracking target or a change in the viewpoint of the camera.
Therefore, a method of increasing the matching score value by deforming (for example, rotating) the template has also been proposed. However, since the processing time is extremely long, it is difficult to track the feature pattern at high speed. Therefore, in order to track feature patterns more reliably and faster,
In the present embodiment, a method of temporally updating the reference pattern for template matching is used.

When the reference pattern is updated temporally, there is a method of updating the reference pattern for each frame or at a constant frame interval. However, it is not possible to update the reference pattern for each frame depending on the movement posture and speed of the tracking target. Not efficient
It is also possible that errors in the tracking process are accumulated. Updating the reference pattern at regular frame intervals is efficient, but it is not easy to set an appropriate pattern update time interval. Therefore, in the present embodiment, the reference pattern is updated and the feature pattern is tracked using the score value of the pattern matching based on the normalized correlation as an evaluation criterion for updating the reference pattern. As described above, the feature points (patterns) are detected, the feature patterns in the image of the first frame are detected, and these are used as the initial reference patterns Ti1 (x, y) (i = 1,..., P).
And

Further, those reference patterns are applied to the time-series image f (x, y, t) (t> 1), pattern matching is performed by normalized correlation, and the threshold value for which the matching score value has been set is set. If less than T _1, to update the feature pattern in the previous frame image as a new reference pattern. In addition, even if the movement posture of the tracking target does not change due to the noise in the image, the matching score value may decrease, so in practice,
Clique value T ₁ of the matching score to be evaluated criteria of the reference pattern updating, it is better to set the around 80%, as described above.

A feature (point) pattern is detected as a reference pattern Ti1 (x, y) from the image of the first frame, and the matching score value is used as a tracking evaluation criterion using pattern matching by normalized correlation. The same object is tracked in the eye image and the third frame image.
Also, depending on the rotation of the target, since the matching score value tracked in the fourth frame image is smaller than the thresholds T _1, which is set to the target pattern at the previous frame image as a new reference pattern. Then, the same target in the image of the fourth frame is tracked using the new reference pattern. By repeating such a reference pattern update process, more reliable feature tracking becomes possible with respect to changes in the movement posture such as rotation of the tracking target.

The tracking result thus obtained is output from the tracking result output unit 8 to the tracking result processing unit 11. The tracking result processing unit 11 analyzes the tracking result by performing the processing described with reference to the flowchart in FIG.

The reason why the analysis is performed without using the obtained tracking result as it is is as follows. In time series images taken continuously, due to changes in environmental light (such as light reflection), defocusing, changes in movement posture due to rotation of the object, cumulative tracking errors due to pattern updates, quantization errors in digital images, etc. It is not always possible to track a moving object at all moments over a certain time interval. Even if the above-described techniques such as the setting of the search area and the updating of the reference pattern are applied, tracking errors and erroneous tracking often occur.

Therefore, in the present embodiment, since the movement of the moving object is generally considered to be continuous, the tracking data of the tracking data is obtained by using the least squares method for the tracked feature point coordinate data. The method of performing the analysis is shown. In step S61, the tracking result of the 2F × P feature point is output from the tracking result output unit 8 to the tracking result processing unit 11. As a result, the tracking result processing unit 11 receives the coordinate values of x and y in the F frame of the feature points of the number P. In step S62, the coefficients of the Nth-order curve using the energy minimizing function are calculated for the input coordinate values.

In step S63, the x-coordinate value and the y-coordinate value of the characteristic point based on the Nth order curve are estimated (calculated). The estimated value and the actually input actual value are used in step S
64, it is determined in step S65 whether the comparison result, that is, the error is greater than a threshold, and if it is determined that the error is greater than the threshold, the tracking trajectory is determined as an uncertain tracking trajectory, and the data Is not used (deleted).

In step S66, it is determined whether or not the analysis of all the tracking trajectories (feature point coordinate values) has been completed.
When it is determined that the processing has not been completed, the process returns to step S62, and the subsequent processing is repeated. When it is determined that the processing has been completed, this follow chart (processing of analyzing the tracking result) is performed.
Is terminated.

The analysis of the tracking image data described above is specifically performed by calculation using the following equation. That is, first, the image f of the first frame
Center coordinates Pi1 (xi1, yi) at (x, y, 1)
1) reference pattern Ti1 (x, y) (i = 1,
.., P), for a time-series image of k frames,
The center coordinates of k sets of target patterns tracked while updating the reference pattern are represented by Pit (xit, yit) (t = 1,
2,..., K). Further, the motion trajectory of the motion target can be represented by an n-th order curve as in the following equation (4).

Anxn + an-1xn-1 + ... + a1x + bnxn + bn-1xn-1 + ... + b1y-1 = 0 (4)

In order to determine the coefficient of the n-th order curve of the equation (4), k ≧ (2n + 1) must be satisfied. The above equation (4) can be rewritten as the following equation (5).

[Mxy] · [Pab] = [I] (5) where

[0066]

(Equation 2)

[0067]

(Equation 3)

[0068]

(Equation 4)

In order to find the coefficient parameter [Pab] of the nth order curve, the following energy function E is introduced, and a solution that minimizes it is found. That is, E = ([Mxy] · [Pab] − [I]) ^T × ([Mxy] · [Pab] − [I]) (9) is defined as an energy function E, and is minimized ( ∂E / ∂
By calculating [Pab] = 0), [Pab] is obtained as in the following equation (10).

[Pab] = ([Mxy] T · [Mxy]) − 1 · [Mxy] T · [I] (10) The tracking trajectory correction processing using the nth-order curve is performed in all the features. By performing the operation on the points, the motion trajectory of the motion target can be more reliably tracked.

The result obtained by tracking the movement trajectory of the movement target (the result output from the tracking result processing unit 11) is used for, for example, restoring a three-dimensional model.

Next, an example in which the movement of a subject is tracked using 28 time-series images will be described with reference to FIGS. FIG. 10 shows the first 1 to 4 frames and the last 25 to 28 frames out of 28 time-series images (frames).
Frame shown. A square block having a cylinder at the center is a subject to be tracked, and shows that the subject is gradually rotating clockwise.

When the feature points are extracted from the image of frame 1 by the processing described with reference to the flowcharts of FIGS. 3 and 4, the result shown in FIG. 11 is obtained. FIG.
In the example shown in (3), 34 feature points are extracted, and a feature pattern (reference pattern) composed of the 34 feature points is shown. Further, when the 28 time-series images are tracked by the above-described processing, the tracking result is as follows.
As shown in FIG. In FIG. 12, the white line is
It shows a trajectory as a result of tracking each feature point.

FIG. 13 shows the result of tracking the second feature point using template matching by normalized correlation. Tracking of the same target by template matching becomes difficult due to rotation of the target, a change in the viewpoint of the camera, and the like. However, more accurate tracking of the feature pattern can be performed by setting a search area or updating a reference pattern. In addition, the accumulated error during tracking may occur due to the rotation of the target, etc., and the tracking trajectory is corrected using the n-th order curve estimated by the least squares method, and a smoother trajectory of the motion of the target is obtained. Obtainable. FIG. 14 shows the result of correcting the motion trajectory of the second feature point shown in FIG. 13 by such a method.

In this way, by tracking and processing the movement of the subject, the automatic tracking of the most important feature points in the restoration of the three-dimensional shape and the movement of the camera by the factor decomposition method using the time-series image can be performed with high accuracy. It can be realized well. In addition, by setting the search area, responding to the deformation of the tracking target, and analyzing the data of the tracking result (trajectory),
It is possible to improve the reliability of tracking in the feature tracking method.

The series of processes described above can be executed by hardware, but can also be executed by software. When a series of processing is executed by software, a program constituting the software is executed by the image processing apparatus 1 as dedicated hardware.
It is installed in, for example, a general-purpose personal computer or the like, which can execute various functions by installing a computer incorporated in the PC or various programs.

Next, referring to FIG. 15, regarding a medium used for installing a program for executing the above-described series of processes in a computer and making the computer executable, the computer is a general-purpose personal computer. The following is an example of the case.

As shown in FIG. 15A, the program can be provided to the user in a state where the program is previously installed in a hard disk 32 or a semiconductor memory 33 as a recording medium built in the personal computer 31.

Alternatively, the program is executed as shown in FIG.
As shown in (B), floppy disk 41, CD-ROM
(Compact Disk-Read Only Memory) 42, MO (Magne
to-Optical) 43, DVD (Digital Versatile Disk) 4
4. It can be temporarily or permanently stored in a recording medium such as a magnetic disk 45 or a semiconductor memory 46 and provided as package software.

Further, as shown in FIG. 15C, the program is wirelessly transferred from the download site 51 to the personal computer 31 via the artificial satellite 52 for digital satellite broadcasting, or transmitted from the local area network or the Internet. The data can be transferred to the personal computer 31 via the network 61 by wire, and can be stored in a built-in hard disk or the like in the personal computer 31.

The medium in the present specification has a broad concept including all these media.

The personal computer 31, for example,
As shown in FIG. 16, a CPU (Central Processing Unit)
72 are built-in. An input / output interface 75 is connected to the CPU 72 via a bus 71.
From the user via the input / output interface 75
When a command is input from an input unit 77 including a keyboard, a mouse, and the like, a program stored in a ROM (Read Only Memory) 73 corresponding to the semiconductor memory 33 in FIG. . Alternatively,
The CPU 72 is a program stored in the hard disk 72 in advance, transferred from the satellite 52 or the network 61, received by the communication unit 78, and further installed in the hard disk 32 or the floppy disk 41 attached to the drive 79. CD-R
The program read from the OM 42, the MO disk 43, the DVD 44, or the magnetic disk 45 and installed on the hard disk 32 is stored in a RAM (Random Access Memory).
y) Load to 44 and execute. Further, the CPU 72 outputs the processing result to a display unit 76 such as an LCD (Liquid Crystal Display) via the input / output interface 75 as necessary.

In this specification, steps for describing a program provided by a medium are not limited to time-series processing, but may be performed in parallel according to the described order. Alternatively, it also includes individually executed processing.

[0084]

As described above, according to the image processing apparatus according to the first aspect, the image processing method according to the fourth aspect, and the medium according to the fifth aspect, each pixel of the input image is differentiated. Find the eigenvalue of the feature matrix defined using the image information,
A point whose eigenvalue is equal to or greater than a threshold is extracted as a feature point,
A predetermined number of pixels including the extracted feature points is set as a reference pattern, a degree of similarity with the reference pattern is calculated in a predetermined area of the image, and an area where the degree of similarity is equal to or more than a predetermined value is defined as a plurality of By searching over a predetermined subject in the image, the accuracy of feature tracking can be improved.

According to the image processing apparatus of the sixth aspect, the image processing method of the ninth aspect, and the medium of the tenth aspect, a feature point is extracted from an input image and extracted. A predetermined number of pixels including a feature point is set as a reference pattern, a search area of a predetermined size is set in an image, and a similarity with the reference pattern is calculated in the search area. If it is not determined to be larger, the search area is reset, and the area where the similarity is determined to be larger than the predetermined value is searched for over a plurality of images, thereby tracking a predetermined subject in the image, and The calculation of the similarity and the comparison with the predetermined value are repeatedly performed until it is determined that the degree is larger than the predetermined value, or until it is determined that the reset search area is equal to or larger than the predetermined size. So that It is possible to increase the accuracy of the symptoms tracking.

An image processing apparatus according to claim 11,
According to the image processing method of the present invention, a feature point is extracted from an input image, and a predetermined number of pixels including the extracted feature point is set as a reference pattern. Then, the similarity with the reference pattern is calculated in a predetermined area in the image, and if the similarity is not determined to be larger than the predetermined value, the reference pattern is reset and the similarity is determined to be larger than the predetermined value. A predetermined subject in the image is tracked by searching for the region in the case where a plurality of images have been obtained, and the resetting of the reference pattern and the calculation of the similarity are repeated until the similarity is determined to be larger than the predetermined value. Since it is performed, it is possible to increase the accuracy of feature tracking.

[Brief description of the drawings]

FIG. 1 is a diagram for describing conventional feature tracking.

FIG. 2 is a diagram illustrating a configuration of an image processing apparatus to which the present invention has been applied.

FIG. 3 is a flowchart illustrating a feature point extraction process.

FIG. 4 is a flowchart following FIG. 3;

FIG. 5 is a diagram illustrating extraction of a feature point.

FIG. 6 is a flowchart illustrating search area setting and reference pattern setting.

FIG. 7 is a diagram illustrating setting of a search area.

FIG. 8 is a diagram illustrating setting of a reference pattern.

FIG. 9 is a flowchart illustrating processing of a tracking result.

FIG. 10 is a diagram showing a time-series image for which it is desired to obtain a tracking result.

FIG. 11 is a diagram showing a result of extracting feature points.

FIG. 12 is a diagram showing a tracking result as a trajectory.

FIG. 13 is a graph showing a tracking result.

FIG. 14 is a graph when the result shown in the graph of FIG. 13 is corrected.

FIG. 15 is a diagram illustrating a medium.

16 is a block diagram showing an internal configuration of the personal computer shown in FIG.

[Explanation of symbols]

1 image processing unit, 2 image input unit, 3 feature point extraction unit, 4 search area setting unit, 5 reference pattern setting unit, 6 switch, 7 normalized pattern matching unit, 8 tracking result output unit, 9 score value judgment unit,
10 Reference pattern update unit, 11 Tracking result processing unit

Claims (15)

[Claims] An input unit for inputting an image, and an eigenvalue of a feature amount matrix defined using differential image information is obtained for each pixel of the image input by the input unit, and the eigenvalue is equal to or larger than a threshold. Extracting means for extracting a point as a feature point; setting means for setting a predetermined number of pixels including the feature point extracted by the extracting means as a reference pattern; and setting means within a predetermined area of the image. Calculating means for calculating the degree of similarity with the reference pattern set by the method, and searching for a region in which the degree of similarity calculated by the calculating means is equal to or more than a predetermined value over a plurality of images, thereby determining the predetermined degree of the image. And a tracking unit for tracking the subject. 2. The image processing apparatus according to claim 1, wherein the calculating unit calculates the similarity using a normalized correlation method. 3. The image processing apparatus according to claim 1, wherein the tracking unit uses a multidimensional function curve obtained by using a least squares method based on a search result over a plurality of images as a tracking result. apparatus. 4. An input step of inputting an image, and an eigenvalue of a feature matrix defined using differential image information for each pixel of the image input in the processing of the input step is obtained. An extraction step of extracting a point equal to or larger than a threshold value as a feature point; a setting step of setting a predetermined number of pixels including the feature point extracted in the processing of the extraction step as a reference pattern; A calculating step of calculating a similarity with the reference pattern set in the processing of the setting step, and searching for a region in which the similarity calculated in the processing of the calculating step is equal to or more than a predetermined value over a plurality of images. A tracking step of tracking a predetermined subject in the image. 5. An extraction step of obtaining an eigenvalue of a feature amount matrix defined using differential image information for each pixel of the input image, and extracting a point whose eigenvalue is equal to or larger than a threshold value as a feature point. A setting step of setting a predetermined number of pixels including the feature points extracted in the processing of the extraction step as a reference pattern; and the reference pattern set in the processing of the setting step in a predetermined area of the image. Calculating a similarity of a plurality of images, and searching for a region in which the similarity calculated in the processing of the calculating step is equal to or more than a predetermined value over a plurality of images, thereby tracking a predetermined subject of the image. And a medium for causing a computer to execute a program comprising steps. 6. An input unit for inputting an image, an extraction unit for extracting a feature point from the image input by the input unit, and a predetermined number of pixels including the feature point extracted by the extraction unit as a reference. Setting means for setting as a pattern, search area setting means for setting a search area of a predetermined size in the image, and setting by the setting means in the search area set by the search area setting means Calculating means for calculating the degree of similarity with the reference pattern; determining means for determining whether the degree of similarity calculated by the calculating means is greater than a predetermined value; A resetting means for resetting the search area when it is not determined to be large, and an area when the similarity is determined to be larger than a predetermined value by the determining means. By searching across the image, and a tracking means for tracking a predetermined subject of the image, the calculation unit, the processing of the determination means, and resetting means,
The image is repeatedly performed until the similarity is determined to be larger than a predetermined value, or until the search area set by the resetting means is determined to be larger than a predetermined size area. Processing equipment. 7. The image processing apparatus according to claim 6, wherein the calculating unit calculates the similarity using a normalized correlation method. 8. The image processing apparatus according to claim 6, wherein said tracking means uses a multidimensional function curve obtained by using a least squares method based on a search result over a plurality of images as a tracking result. apparatus. 9. An input step of inputting an image, an extraction step of extracting a feature point from the image input in the processing of the input step, and a predetermined number including the feature points extracted in the processing of the extraction step A setting step of setting a pixel as a reference pattern, a search area setting step of setting a search area of a predetermined size in the image, and within the search area set in the processing of the search area setting step, A calculating step of calculating a similarity with the reference pattern set in the processing of the setting step; a determining step of determining whether the similarity calculated in the processing of the calculating step is larger than a predetermined value; If the similarity is not determined to be greater than the predetermined value in the processing of the determining step, a resetting step of resetting the search area; A tracking step of tracking a predetermined subject in the image by searching a plurality of images for an area when the similarity is determined to be larger than a predetermined value in the processing of the map, The processing of the determining step and the resetting step is performed until the similarity is determined to be larger than a predetermined value, or when the search area set in the processing of the resetting step is larger than an area of a predetermined size. An image processing method which is repeatedly performed until a determination is made. 10. An extraction step of extracting a feature point from the input image, a setting step of setting a predetermined number of pixels including the feature point extracted in the processing of the extraction step as a reference pattern, A search area setting step of setting a search area of a predetermined size within the area; and a similarity of the reference pattern set in the processing of the setting step in the search area set in the processing of the search area setting step. A calculating step of calculating a degree, a determining step of determining whether or not the similarity calculated in the processing of the calculating step is greater than a predetermined value, and determining that the similarity is greater than a predetermined value in the processing of the determining step. If it is not determined, it is determined that the similarity is larger than a predetermined value in the resetting step of resetting the search area and the processing of the determining step And a tracking step of tracking a predetermined subject in the image by searching for a region in a plurality of images. In the processing of the calculating step, the determining step, and the resetting step, the similarity is a predetermined value. The program is repeatedly executed until it is determined that the search area is larger or the search area set in the processing of the resetting step is determined to be larger than an area of a predetermined size. Medium to be made. 11. An input unit for inputting an image, an extraction unit for extracting a feature point from the image input by the input unit, and a predetermined number of pixels including the feature point extracted by the extraction unit as a reference. Setting means for setting as a pattern; calculating means for calculating a similarity with the reference pattern set by the setting means in a predetermined area in the image; and wherein the similarity calculated by the calculating means is a predetermined value. Determining means for determining whether or not the similarity is greater than a predetermined value; resetting means for resetting the reference pattern when the similarity is not determined to be greater than a predetermined value; Tracking means for tracking a predetermined subject in the image by searching for a region in which the degree is determined to be larger by a predetermined value over a plurality of images; Calculating means, the processing of the determination means, and resetting means,
An image processing apparatus, wherein the processing is repeatedly performed until it is determined that the similarity is larger than a predetermined value. 12. The method according to claim 11, wherein the calculating unit calculates the similarity using a normalized correlation method.
An image processing apparatus according to claim 1. 13. The image processing apparatus according to claim 11, wherein said tracking means uses a multidimensional function curve obtained by using a least-squares method based on a search result over a plurality of images as a tracking result. apparatus. 14. An input step of inputting an image, an extraction step of extracting feature points from the image input in the processing of the input step, and a predetermined number including the feature points extracted in the processing of the extraction step. A setting step of setting a pixel of the image as a reference pattern; a calculating step of calculating a similarity with the reference pattern set in the processing of the setting step within a predetermined region in the image; and a processing of the calculating step. A determining step of determining whether the calculated similarity is greater than a predetermined value; and a step of resetting the reference pattern if the similarity is not determined to be greater than the predetermined value in the processing of the determining step. A setting step; and searching a plurality of images for an area when the similarity is determined to be greater than a predetermined value in the processing of the determining step. A tracking step of tracking a predetermined subject in the image, wherein the processing of the calculating step, the determining step, and the resetting step are repeatedly performed until the similarity is determined to be larger than a predetermined value. An image processing method characterized by the following. 15. An extracting step of extracting a feature point from the input image, a setting step of setting a predetermined number of pixels including the feature point extracted in the processing of the extracting step as a reference pattern, and Calculating a similarity with the reference pattern set in the processing of the setting step in a predetermined area of the area; and determining whether the similarity calculated in the processing of the calculation step is larger than a predetermined value. And a resetting step of resetting the reference pattern if the similarity is not determined to be greater than a predetermined value in the processing of the determining step; A tracking step of tracking a predetermined subject in the image by searching a plurality of images for an area determined to be larger than the predetermined value; Made, the calculation step, decision step, and the process of re-setting step, the medium to execute the program, wherein the degree of similarity is repeatedly performed until it is determined to be greater than the predetermined value to the computer.