JP2940247B2 - Moving object contour detection device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for realizing highly efficient compression of moving image data in TV, HDTV, videophone, etc.
BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a moving object contour detection device applicable to a method of extracting a component object for synthesizing an image in the creation of a TV program, a movie, or the like, an extraction method of a search key image for constructing a moving image database, and the like.

[0002]

2. Description of the Related Art Conventionally, in detecting a contour of a moving object in a moving image, clustering is performed based on texture and color information of the image and a velocity vector calculated for each pixel.
A method of detecting the contour of the cluster area has been adopted.

[0003] For example, in the document "Motion image segmentation based on sequential update algorithm: Ishii et al., IEICE Pattern Recognition and Understanding Study Group Report, PRU90-
No. 1 "reports a method of generating one cluster area based on this policy. In this method, first,
At time t, a moving object region candidate is obtained by clustering based on the texture and color information. Next, each pixel of the obtained candidate of the moving object region is shifted by the velocity vector to generate a predicted image. Then, clustering of pixels having a large difference (error) between the predicted image and the actual image at time t + 1 is performed again to change the cluster group.

[0004] The basic configuration of a conventional apparatus will be described below with reference to FIG. Reference numeral 201 denotes a moving image memory that stores moving image data input along the flow of time, 202 denotes an arithmetic unit that calculates a velocity vector as a definite value at each pixel in the moving image memory, and 203 denotes texture information at each pixel. Computing device for calculating color information
Is an arithmetic unit that detects the area of the moving object by clustering the information calculated by the arithmetic units 202 and 203 and performs pixel grouping, and 205 is an arithmetic unit that generates the outline of the area.

[0005]

Such a conventional technique has the following essential problems.

(1) This technique is based on the assumption that a color, a texture, and a velocity vector for each pixel correspond to one cluster within an area of one moving object, that is, each pixel has the same value. Therefore, in a situation where this is not possible, the accuracy of region detection is extremely reduced. In fact, in most natural images, the color (color) or texture (pattern) of one object is rarely one.

Also, it is impossible that all velocity vectors are equal at each position in the moving object area.
Even if the object is a perfect rigid body, in the real world, 3
Since a motion is performed in a dimension, in a moving image that is a result of projecting the motion in two dimensions, it is generally impossible that all pixels have the same speed.

(2) Calculating the velocity vector with high accuracy involves an inherently difficult point, which may cause a large error. In particular, the phenomenon of movement disappears near the boundary of the region of the moving object, so it is impossible to even assume the existence of speed. This is shown using FIG.

At time t in FIG. 3, the portion of the area B that is in contact with the area A is hidden behind the area A at time t + 1, as indicated by hatching. The motion in the video refers to the phenomenon that the region appears to shift to a slightly distant position at the next time, and it is not the motion that disappears and disappears, and therefore the speed in such a region is naturally Vectors cannot be defined and calculated.

[0010]

According to the present invention, in order to solve such a problem, a grid position (x, y, t) in a three-dimensional space obtained by expanding a time axis of a moving image in a depth direction is a moving image. A conversion means for converting to an address in the image data storage means; and a grid position (x,
y, t), and based on the moving image data in the vicinity of the grid position (x, y, t) output from the moving image data storage means, calculates the contour feature at the grid position. Contour feature calculating means, contour candidate grid point generating means for generating a set of grid point candidates constituting the contour in a three-dimensional space, and a contour surface generated by the set of contour candidate grid points in a three-dimensional space. Contour candidate grid point generating means, using both data of a curved surface smoothness calculating means for calculating smoothness, a contour feature amount calculated by the contour feature calculating means, and smoothness of a curved surface calculated by the curved surface smoothness calculating means as evaluation criteria. Generated
A search means is provided for searching a set of lattice points corresponding to an appropriate contour of a moving object from a set of candidate grid points constituting the contour.

[0011]

When the time axis of the moving image data is viewed in a three-dimensional space developed in the depth direction, one object region in the moving image corresponds to one solid in this space. This three-dimensional surface corresponds to the trajectory of the contour in the time direction. Therefore, the contour detection of the moving object can be regarded as a problem of searching for the three-dimensional surface (curved surface). If the color and texture information and motion information are expressed as a feature that indicates the degree of reliability as a contour in the relationship between them and the contour of the moving object, if this constraint is applied in the search for the three-dimensional surface, Can be interpreted.

The operation of the present invention will be described below. 1) When the contour of the moving object is designated, the contour candidate lattice point generating means expands the time axis in the depth direction in the vicinity of the designated contour lattice point to form a set of lattice points constituting a three-dimensional surface in a three-dimensional space. Generate candidates.

[0013] 2) The curved surface smoothness calculating means calculates a contour grid point set candidate generated by the contour candidate grid point generating means.
The smoothness of the curved surface created by the set of grid points in the three-dimensional space is calculated according to a predetermined calculation formula.

3) The contour feature calculating means inputs the data near the grid point from the moving picture data storage means via the converting means to the grid point candidate generated by the contour candidate grid point generating means, Contour features,
That is, the degree of reliability (probability) at which the position is included in the contour is calculated.

[0015] 4) The search means calculates an appropriate three-dimensional surface from the set of grid points generated by the contour candidate grid point generating means, ie, the information of the contour feature calculated by the contour feature calculating means. The search is performed based on the information on the smoothness of the curved surface generated by the curved surface smoothness calculating means.

The basis of the validity of adding the information on the smoothness of the curved surface to the evaluation of the three-dimensional surface (curved surface) is that if it can be assumed that the motion of the object progresses continuously, the three-dimensional surface is roughly in the time axis direction. Has the property of being smooth.
(See FIG. 4) As described above, the present invention is to search for a contour based on two types of constraint information. The first constraint information is a contour feature, that is, a degree of certainty that a pixel is included in the contour. This information is local information that can be calculated directly from the image. This is in contrast to the use of the fixed information including the error of the pixel speed vector in the past.

The second constraint information is constraint information of smoothness with respect to the trajectory of the contour in the three-dimensional space. This constraint is a global (non-local) constraint, and a smooth contour can be extracted by adding the constraint to the constraint. An appropriate contour is detected using the balance of the above two types of information as an evaluation criterion.

[0018]

An embodiment of the present invention will be described below with reference to FIG.

This is a system in which a user can automatically detect the outline of a specific moving object by specifying the vicinity of the outline of the moving object in an image displayed on the display of the console.

Referring to FIG. 1, reference numeral 101 denotes a storage device for inputting moving image data in a time sequence, and comprises N frame memories. Reference numeral 102 denotes a console device for designating the vicinity of the contour of the moving object to be detected while the user looks at the display. Reference numeral 103 denotes a three-dimensional grid position (x,
y, t) (x, y are positions in the frame: t is time),
This is a conversion device that converts the address of a pixel in a specific frame. Reference numeral 104 denotes a processor that calculates a contour feature, that is, a degree of reliability as a contour of a grid point candidate, for a grid point candidate generated by the contour candidate grid point generation processor 105 according to a predetermined calculation formula. . The calculation formula is described in the document "Differential-product-sum operator for video classification: Shigeru Ando, Transactions of the Society of Instrument and Control Engineers Vol.25, No4, pp496-503, (1
Formula for the appearance feature extraction operator (velocity boundary feature extraction operator) reported in 989)

[0021]

(Equation 1)

Is used. Reference numeral 106 denotes a processor that calculates the smoothness of a curved surface created in the three-dimensional space by the set of contour candidate lattice points generated by 105 according to a predetermined calculation formula. The formula is:

[0023]

(Equation 2)

Is used. In (Equation 2), X is an arbitrary point on a curved surface, and is given as a function of a time parameter t and a line element parameter s on the contour of the moving object, as shown in FIG. The parameter α is introduced to make a difference in the strength of the smoothness constraint between the t direction and the s direction.

107 is defined on the basis of the information on the contour feature and smoothness calculated by the processors 104 and 106 for the grid points of the contour candidates, respectively.

[0026]

(Equation 3)

This is a search device for searching for a three-dimensional surface where the value of becomes smaller. The mechanism of the grid point generation of the contour candidate grid point generation processor 105 and the search control mechanism of the search device 107 will be described below.

In this embodiment, in order to improve the efficiency of the search, as shown in FIG. 6, a plane sequence Hk (k = 0)
Search for the curve of the cross section by... N).

The basics of this mechanism are: The contour grid point set generation processor 105 determines the plane Hk (k = 0... N) based on the already searched contour grid points.

2. On the plane Hk, the processor 105 successively generates contour grid point candidate sets. 3. From the candidates for the contour grid points, the search device 107 sets two adjacent grid points as a set and repeats the search for this set. It is.

[0031] Hereinafter, will be described method of determining the plane sequence H _k with reference to FIG. Thereafter, the grid point X _{j, k} is _defined on the intersection of the plane H _k and the plane t = t ₀ + j (t ₀ is the time of the frame specified by the user, j = 0, 1, 2, 3,...) The grid points already determined as contour grid points are shown. Also, the grid point Z
_{j and k} represent arbitrary grid points generated by the 106 contour candidate grid point processors on the same intersection line.

A. When k ≧ 2 A point Y _k displaced from the lattice point X _{0, k-1} (X _0,0 , X _0,1 has already been searched) within the plane t = t ₀ by a distance 1 in the contour direction.
Through the vector perpendicular to the contour direction

[0033]

(Equation 4)

And the vector

[0035]

(Equation 5)

A plane determined by the two vectors
You. Here, the contour direction is the plane t = t ₀Already explored within
Vector

[0037]

(Equation 6)

Given as Also, vector

[0039]

(Equation 7)

Is a rough velocity vector of this moving object region.

[0041]

(Equation 8)

Is defined based on the components of To calculate this velocity vector, refer to the document "Velocity vector distribution measurement system using spatio-temporal differentiation of images: Shigeru Ando, Transactions of the Society of Instrument and Control Engineers, 22-12, pp 1330-1336 (19
86) ", and the following formula is used.

[0043]

(Equation 9)

B. When k = 0,1 (H ₀ and H ₁ ): Determined as follows based on information input by the user.

The user specifies the time (time and frame order in the video) and the four points in the video through the console device 202 as shown in FIG. Three-dimensional lattice position P ₀ (x ₀ , y ₀ , t ₀ ), P
₁ (x ₁ , y ₁ , t ₀ ), P ₂ (x ₂ , y ₂ , t ₀ ), P
₃ (x ₃ , y ₃ , t ₀ ). Here, the line element (short line segments) P ₀ P ₁ is taken on the approximate contour of at animal body at time t _0, the line element P ₂ P ₃ is approximately in each and P ₀ P ₁ It shall intersect at approximately right angles at point P _4. Plane H ₀ is the H _k (k ≧ 2) of the definitions mentioned above, and the point Y ₀ and the point P _4, vector (Equation 4), the vector

[0046]

(Equation 10)

Is determined as follows. Plane H₁When determining
Point X_0,0Is already determined, so point X _0,0Vector from

[0048]

[Equation 11]

A point deviated by a distance 1 in the direction is defined as Y ₁ . The vector (Equation 4) is given by a vector (Equation 9) similarly to the case of H ₀ . Also, the vector (Equation 7) is calculated for all k (k =
0, 1, 2,...).

Hereinafter, the processor 205 and the search device 207 will be described.
There cooperatively, a description will be given of a mechanism to continue to search for the contour grid point in the plane H _k.

The basic mechanism is described in the document “A Formal B
asis for the Heuristic Determina-tion of Minimum C
ost Paths: PETER E.HART, et al., IEEE TRANSACTIONS
ON SYSTEMS SCIENCE AND CYBERNETICS, pp100-107, (7,19
68) ”based on the A * algorithm reported.

1. Within the plane t = t _{0 The} processor 105 generates a set S (Y _k ) of contour candidate lattice points within the neighborhood of the lattice point Y _k within the plane t = t ₀ , and
04 to the contour feature calculation processor and 107 search device. The processor 104 calculates a contour feature for the grid points Z _{0, k} of all elements of S (Y _k ), and
Returns the value to

The search device 107 defines a set of a grid point Y _k and a grid point Z ₀ , _k as one node in the A * algorithm, and uses it as a search unit. An arbitrary node (Y _k , Z _{0, k} ) is included in the search candidate node set OPEN as a start node. Node cost is grid point Z
Let the value of the contour feature be _{0, k} . The search device 107 selects one node having the highest evaluation from the element nodes of the search candidate node set OPEN according to the A * algorithm. Next, assuming that Z _{0, k} is MZ ₀ , _k , nodes (Y _k , MZ
_{0, k} ) from the set OPEN to the searched node set CLOSE
Transfer to Further, the search device 107 sends MZ _{0, k} to the processor 105.

2. In the plane t = t ₀ +1 The processor 205 sets a new contour candidate lattice point set S (M) in the vicinity of the lattice point MZ _{0, k} within the plane t = t ₀ +1.
Z _{0, k} ) is generated and sent to the contour feature calculation processor 104 and the search device 107. 204 is a set S (M
The contour feature is calculated for the grid points Z _{1 , k} of all the elements of Z _{0, k} ), and the value is returned to the search device 107.

Reference numeral 107 denotes an arbitrary element lattice point Z _{1, k} and M
As a set of Z _{0, k,} it generates a new node _{(MZ 0, k, Z 1} , k), placed in the search candidate node set OPEN. The cost of this node is now defined by the sum of the values of the contour features at the two grid points. Next, 107 selects one node with the highest evaluation from the set of search candidate nodes OPEN according to the node selection criterion of the A * algorithm and sends it to the processor 105. At the same time, this node is moved to the searched node set CLOSE.

3. Within the plane t = t ₀ + m (m = 2, 3, 4
...) Assuming that the search device 107 has searched for a node (Z _m − _{1, k} , Z _{m, k} ) in the search candidate node set OPEN, the search device 107 sets Z _{m, k} as MZ _{m, k.} , To the processor 105. The processor 105 calculates the plane t of the lattice point MZ _{m, k}
= T ₀ + m + 1 A new set S (MZ _{m, k} ) of candidate contour grid points is generated in the vicinity of the point and sent to the search device 107 and the contour feature calculation processor 104. Search device 107
Are the arbitrary elements Z _{m + 1, k} and MZ _{m, k} of the set S (MZ _{m, k} )
, A new node is generated, and a search candidate node set OP
Add to EN. The cost of the node (Z _{m, k} , Z _{m + 1, k} ) generated as a continuation node of the node (Z _{m-1, k} , Z _{m, k} ) passes from the start node to this node The sum of the cost of the obtained nodes is _added to the contour feature at Z _{m + 1, k} and the information of the smoothness calculated by the processor 106.

[0057]

(Equation 12)

Is defined as the value added. 4. In this way, it is assumed that the contour grid points are determined as a point sequence {X _{m, r} | m = 0, 1, 2,... N} (N is the number of target frames) on the plane H _r (r ≦ k). Then, the processor 205 determines the plane H _{k + 1} based on the points X _{0, k-1} and X _{0, k} by the above-described method, and again searches for the cross-sectional curve in the plane H _{k + 1} . Do.

[0059]

As described above, according to the present invention, contour detection is performed using the overall balance of two types of constraint information as an evaluation criterion, so that highly accurate contour detection can be realized and used for TV and movie creation. This is an invention that is particularly effective in a technical field that requires high contour detection accuracy, such as clipping of video components.

[Brief description of the drawings]

FIG. 1 is a block diagram of a moving object contour detection device according to an embodiment of the present invention.

FIG. 2 is a block diagram showing a conceptual configuration of a moving object contour detection device according to a conventional technique.

FIG. 3 is an explanatory diagram showing that a velocity cannot be defined at a region boundary of an object;

FIG. 4 is a three-dimensional surface diagram in a three-dimensional space.

FIG. 5 is a representation diagram of grid points on a three-dimensional surface.

FIG. 6 is an explanatory diagram of how to determine a plane Hk.

FIG. 7 is a diagram showing a designation of a moving object to be detected by a user.

[Explanation of symbols]

 Reference Signs List 101 moving image data storage means 102 conversion means 103 contour feature calculation means 104 contour candidate lattice point generation means 105 curved surface smoothness calculation means 106 search means

────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A-2-212982 (JP, A) JP-A-1-17170 (JP, A) (58) Fields investigated (Int. Cl. ⁶ , DB name) G06T 7/20

Claims (1)

(57) [Claims] 1. A moving image data storage means for storing moving image data inputted along a time flow, and a lattice point position (x, y) in a three-dimensional space in which a time axis of the moving image is expanded in a depth direction. , T) to the address of a storage area of the moving image data storage means, and outputs a grid position (x, y, t) in a three-dimensional space to the conversion means.
Contour feature calculating means for calculating a contour feature amount at a grid position based on moving image data near the grid position (x, y, t) output from the moving image data storage means; A contour candidate grid point generating means for generating a set of grid point candidates in a three-dimensional space and outputting the set to the contour feature calculating means, and a set of grid point candidates generated by the contour candidate grid point generating means. Input and the set of grid point candidates is 3
The surface smoothness calculating means for calculating the smoothness of the curved surface created in the three-dimensional space, the contour feature amount calculated by the contour feature calculating means, and the smoothness of the curved surface calculated by the curved surface smoothness calculating means are evaluated. An animal comprising a search unit for searching a set of grid point candidates generated by the outline candidate grid point generation unit for a set of grid points corresponding to an appropriate outline of the moving object as a reference; Body contour detection device.