JP3330348B2 - Video search method and apparatus, and recording medium storing video search program - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a video search method and apparatus for obtaining a similar section from a video to be searched, using a time-series change of a feature amount extracted from an input video as a search key, and a video search. The present invention relates to a recording medium on which a program is recorded.

[0002]

2. Description of the Related Art There are the following two conventional techniques for retrieving a video based on the similarity between a search key specified by a user and a feature extracted from the video.

The first is a method of designating a feature quantity extracted from a video as a search key. In the system described in "Integrated System of Heterogeneous Search Methods for Video Data" (10th Data Engineering Workshop, 1999), color distribution in a frame and its moving direction are extracted as feature amounts. The user searches for an image corresponding to the search key by designating the color and the moving direction of the object as the search key.

[0004] A second method is a method of designating an image as a search key by exemplifying a video. “QUICK AU
DIO RETRIEVAL USING ACTIV
ESEARCH ”(ICASSP, 1998), it is possible to search for a video that is to be searched and find a video that matches the video specified by the search key. For the search object, the signal is divided into appropriate units, and the spectrum of the feature is calculated in advance. For the search key, the spectrum is calculated in the same manner for the specified video, and the obtained histogram of the spectrum is obtained. The search is performed by sequentially scanning the search target spectrum and calculating the similarity with the histogram of the search key.A section in which the similarity exceeds the threshold is set as the search result.

[0005]

However, in the former method, only a simple search key such as "red to right" can be used as a search key. Therefore, there is a problem that a search in which the moving direction changes with time cannot be performed.

In the latter case, the order of the time series is neglected because a histogram of a spectrum is used as a search key. Therefore, if the search key includes reverse playback or a playback key whose playback order is different, the section is also searched. In addition, since this method does not take into account the temporal expansion and contraction of the feature amount, as shown in FIG. There is a problem that can not cope.

SUMMARY OF THE INVENTION The present invention has been made in view of the above circumstances, and provides a video search method and a video search method capable of designating a time-series change in a feature amount of a video as a search key and capable of coping with temporal expansion and contraction of the feature amount. It is an object of the present invention to provide a device and a recording medium recording a video search program.

[0008]

According to a first aspect of the present invention, there is provided an image processing apparatus comprising: a search target image which is obtained by using a time-series change of a feature amount extracted from an input image as a search key; A search target video input step of inputting a search target video as a search target video from a video search method for obtaining a similar section from a search target video, and a time series of frame luminance as a time series feature amount from the search target video is standardized. A standard pattern extracting step for extracting as a pattern, a standard pattern storing step for recording the standard pattern, a search key video inputting step for inputting a search key video which is a video serving as a search key, and a time series from the search key video. A feature pattern extraction step of extracting a time series of frame luminance as a feature amount as a feature pattern; Wherein as to all partial patterns which can be selected, the inter-pattern distance required is minimized by the inter-pattern distance function defined in advance from
Based on a plurality of inter-pattern distance obtaining steps obtained by performing an inter-pattern distance obtaining step of performing matching by expanding and contracting a pattern nonlinearly to obtain an inter-pattern distance, the partial pattern similar to the feature pattern. A similar section search step for narrowing down
A similar section output step of outputting one or a plurality of the partial patterns narrowed down in the similar section search step.

According to a second aspect of the present invention, in the first aspect of the invention, the feature pattern extracting step and the standard pattern extracting step are performed as time-series feature amounts from the search key image and the search target image. The point is that the coordinates of the object in the frame are extracted instead of the luminance of the frame.

According to a third aspect of the present invention, in the first aspect of the present invention, the feature pattern extracting step and the standard pattern extracting step are performed as time-series feature amounts from the search key image and the search target image. The point is that camera motion is extracted instead of frame luminance.

According to a fourth aspect of the present invention, there is provided a video search apparatus for obtaining a similar section from a video to be searched by using a time-series change of a feature amount extracted from an input video as a search key. Search target video input means for inputting a search target video which is a target video, and standard pattern extraction means for extracting a time series of frame luminance as a standard pattern from the search target video as a time series feature amount,
Standard pattern storage means for recording the standard pattern, search key video input means for inputting a search key video which is a video serving as a search key, and a time series of frame luminance as a time series feature amount from the search key video. A characteristic pattern extracting means for extracting the characteristic pattern as a characteristic pattern, such that the inter-pattern distance obtained by a predefined inter-pattern distance function is minimized for all the partial patterns that can be selected from the standard pattern. Features putter
A pattern distance obtaining means for performing matching by expanding and contracting the pattern in a non-linear manner to obtain a pattern distance, and the partial pattern similar to the feature pattern based on a plurality of pattern distances obtained by the pattern distance obtaining means. And similar section output means for outputting one or a plurality of the partial patterns narrowed down by the similar section search means.

According to a fifth aspect of the present invention, in the fourth aspect of the present invention, the characteristic pattern extracting means and the standard pattern extracting means determine a time-series characteristic amount from the search key image and the search target image. The point is that the coordinates of the object in the frame are extracted instead of the luminance of the frame.

According to a sixth aspect of the present invention, in the fourth aspect of the present invention, the feature pattern extracting means and the standard pattern extracting means determine a time-series feature amount from the search key image and the search target image. The point is that camera motion is extracted instead of frame luminance.

According to a seventh aspect of the present invention, there is provided a video search program for obtaining a similar section from a video to be searched by using a time-series change of a feature amount extracted from an input video as a search key. A search target video input procedure for inputting a search target video as a search target video on a recording medium, a standard pattern extraction procedure for extracting a time series of frame luminance as a standard pattern from the search target video as a time series feature amount A standard pattern storage procedure for recording the standard pattern, a search key video input procedure for inputting a search key video serving as a search key video, and a time series of frame luminance as a time series feature amount from the search key video. A feature pattern extraction procedure to be extracted as a pattern, the feature pattern being applied to all partial patterns that can be selected from the standard pattern Performs matching by stretching a feature pattern as a pattern distance obtained by the inter-pattern distance function defined in advance is minimized nonlinearly pattern distance acquisition procedure for obtaining the inter-pattern distance,
A similar section search procedure for narrowing down the partial pattern similar to the feature pattern based on a plurality of pattern distances obtained by the inter-pattern distance acquisition procedure, one or more partial patterns narrowed down in the similar section search procedure And a video search program for executing a similar section output procedure for outputting.

According to an eighth aspect of the present invention, in the invention of the seventh aspect, the feature pattern extraction procedure and the standard pattern extraction procedure are performed as a time-series feature quantity from the search key video and the search target video. The point is that the coordinates of the object in the frame are extracted instead of the luminance of the frame.

According to a ninth aspect of the present invention, in the invention according to the seventh aspect, the feature pattern extracting step and the standard pattern extracting step are performed as a time-series feature amount from the search key image and the search target image. The point is that camera motion is extracted instead of frame luminance.

According to the first, fourth, and seventh aspects of the present invention, a standard pattern is extracted as a feature amount from an input search target video, the standard pattern is stored, and a feature is extracted from the input search key video. Extract feature patterns as quantities,
By associating the stored standard pattern with an arbitrary partial pattern and calculating the inter-pattern distance, narrowing down and outputting a set of a plurality of obtained partial patterns and the inter-pattern distance, the feature amount is obtained from the video. As a search key, it is possible to perform a video search that can specify a time-series change in luminance of a frame extracted as a search key and can cope with temporal expansion and contraction of a feature amount.

According to the present invention, the coordinates of the object in the frame are extracted as time-series feature amounts obtained from the search key image and the search target image, thereby obtaining the object in the image. A video search can be performed using a time-series change in the coordinates of a search key as a search key.

According to the third, sixth, and ninth aspects of the present invention, by extracting camera motion as a time-series feature amount obtained from a search key image and a search target image, a time series of camera motion in the image is extracted. Video search using the change of the search key as a search key.

[0020]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be described below in detail with reference to the drawings.

The embodiment described below relates to a video search system for searching for a similar camera motion from a video to be searched by using a camera motion included in an input video as a search key.

Here, the camera motion means a vertical and horizontal movement of a camera for taking a picture and a zoom operation.

FIG. 1 is a functional block diagram showing a video search device according to an embodiment of the present invention.

In FIG. 1, a video to be searched is input to a video search device by a search target video input means 1.
The input search target video is provided to the standard pattern extracting means 2. For example, MPEG can be used as the video information, but the present invention is not limited to this.

The standard pattern extracting means 2 converts the video to be searched into a standard pattern which is a time-series feature quantity in units of one frame as shown in FIG. 2, for example. The standard pattern is provided to the standard pattern storage means 3. Here, a camera motion extracted from a video is used as the feature amount, but other than that, luminance information of a frame, coordinates of an object in the frame, and the like can be used. In FIG. 2, 1
The rows indicate the feature amounts extracted from one frame, and the columns indicate the types of the feature amounts. The frame number is the frame number from the start point of the video, Vx is the amount of movement of the camera left and right, Vy is the amount of movement of the camera up and down, and Z is the amount of enlargement or reduction by zooming. The camera motion can be extracted by calculating a motion vector, which is, for example, MPEG encoding information, or an optical flow.

The standard pattern storing means 3 records the standard pattern given by the standard pattern extracting means 2. The recorded standard pattern is provided to the inter-pattern distance acquisition means 6.

The search key video input means 4 inputs a video serving as a search key to the video search device. The input video is provided to the feature pattern extraction means 5. For example, MPEG can be used as the video information, but the present invention is not limited to this.

The video input to the feature pattern extraction means 5 by the search key video input means 4 is the same as the standard pattern extraction means 2, for example, as shown in FIG. Is converted to The characteristic pattern is provided to the inter-pattern distance obtaining means 6.
The feature quantity extracted by the feature pattern extraction means 5 needs to be in the same format as the feature quantity extracted by the standard pattern extraction means 2, but the extraction method does not need to be the same.

The inter-pattern distance obtaining means 6 converts a feature pattern to an arbitrary partial pattern selected from a standard pattern so as to minimize the inter-pattern distance obtained by a predefined inter-pattern distance function. Then, matching is performed by expanding and contracting to calculate the distance between patterns. That is, as shown in FIG.
There is a temporal expansion and contraction of the time-series features in the feature pattern
In the case, the time series of features extracted from the input video
Using similar changes as search keys,
In the video search method for finding the section,
Predefined for any selected partial pattern
Pattern obtained by the distance function between patterns
The feature pattern nonlinearly to minimize the distance between
Calculate the distance between patterns by matching
Therefore, based on the chronological change of the feature amount of the video,
Video search that can also respond to temporal expansion and contraction of feature values
Will be able to Pattern distance acquisition means 6
Calculates the inter-pattern distance for all the partial patterns that can be selected from the standard pattern, and provides a set of the selected partial pattern and the inter-pattern distance to the similar section searching means 7. FIG. 3 shows an example of output to the similar section searching means 7. One row represents one set, and the columns represent the start frame number, the end frame number of the partial pattern, and the inter-pattern distance to the feature pattern in order. The more similar the time-series feature amounts, the smaller the distance between patterns. The inter-pattern distance function is, for example, a continuous D as shown in the literature (“Consecutive Word Recognition Using Continuous DP”, Acoustical Society of Japan, Onken Fund, 1978).
P matching may be used. Although the number of partial patterns that can be selected from the standard patterns is generally huge,
By using the continuous DP matching, it is possible to avoid selecting a partial pattern in which the inter-pattern distance is extremely large, and to shorten the time required to acquire the inter-pattern distance. As a distance function d () for providing a distance between feature values in frame units, which is necessary for obtaining a distance between patterns, for example,

[0030]

(Equation 1)

Can be used. Here, i and j are the frame numbers of the standard pattern and the characteristic pattern, respectively.
ω represents a constant that gives the degree of contribution of the camera translation and zoom effect, and the suffixes K and T represent the feature amounts of the standard pattern and the feature pattern, respectively.

The similar section search means 7 narrows down similar area candidates from a set of standard pattern partial patterns and pattern distances, which are candidates for the search results obtained from the inter-pattern distance obtaining means 6, and sends the similar section output means 8 to the similar section output means 8. give.

The narrowing down of candidates is performed in two stages. The first step is to delete overlapping sections. Of the overlapping sections, the section having the smallest inter-pattern distance is adopted, and the rest is deleted. As for the determination of the overlapping section, for example, there is a method of determining whether the sections overlap at a rate equal to or higher than a threshold value or whether the start frame numbers of the sections match. When continuous DP matching is used as the inter-pattern distance function, the latter determination method can be used because overlapping sections tend to have a common start frame due to the nature of continuous DP matching.

The second-stage narrowing is performed by deleting a section having a large distance between patterns. For example, a predetermined number of sections are employed in ascending order of the inter-pattern distance.

The similar section output means 8 outputs a search result by presenting one or more partial patterns narrowed down by the similar section search means 7 in the order of the inter-pattern distance.

The feature pattern extracting means and the standard pattern extracting means extract luminance of a frame or coordinates of an object in the frame as a time-series feature amount from the search key image and the search target image. Alternatively, the present invention can be implemented in the same manner as in the case of extracting the camera motion of the video search device.

In the video search device, the search target video input means, the standard pattern extraction means, the standard pattern storage means, the search key video input means, the feature pattern extraction means, the inter-pattern distance obtaining means, The similar section search means, the similar section output means,
Specifically, it is executed by a computer such as a personal computer (PC) based on a video search program recorded in a predetermined recording medium in advance.

[0038]

As described above, according to the present invention, in a video search system that obtains a similar section from a video to be searched using an input video as a search key, a time-series change in the feature amount of the video can be obtained. Based on this, it is possible to perform a video search that can cope with the temporal expansion and contraction of the feature amount.

For example, in a soccer scene search system incorporating the present invention, when a video such as a corner kick is input as a search key, a video such as a similar corner kick can be searched from the video of the entire game.

[Brief description of the drawings]

FIG. 1 is a functional block diagram illustrating a video search device according to an embodiment of the present invention.

FIG. 2 is an example of a feature pattern output by a feature pattern extraction unit and a standard pattern extraction unit in FIG. 1, in which one row represents a feature amount of one frame, and a column represents a type of the feature amount.

FIG. 3 is an output example of the inter-pattern distance obtaining means of FIG. 1, in which one row represents a set of one partial pattern and the inter-pattern distance, and the columns are sequentially the start frame number of the partial pattern and the end frame number of the partial pattern. , The distance between patterns.

FIG. 4 is an example of a similar feature pattern of a video, which has a time-series feature amount with time expansion and contraction.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Search target video input means 2 Standard pattern extraction means 3 Standard pattern storage means 4 Search key video input means 5 Feature pattern extraction means 6 Inter-pattern distance acquisition means 7 Similar section search means 8 Similar section output means

Claims (9)

(57) [Claims] 1. A video search method for obtaining a similar section from a video to be searched by using a time-series change of a feature amount extracted from an input video as a search key, wherein the video to be searched is a video to be searched. A search target video input step of inputting a video; a standard pattern extraction step of extracting a time series of frame luminance as a standard pattern from the search target video as a standard pattern; a standard pattern storage step of recording the standard pattern A search key video input step of inputting a search key video which is a video serving as a search key; a feature pattern extraction step of extracting a time series of frame luminance as a feature pattern from the search key video as a time series feature amount; The feature pattern is defined in advance for all partial patterns that can be selected from the standard pattern. The characteristic pattern is nonlinearly expanded and contracted so as to minimize the inter-pattern distance obtained by the inter-pattern distance function, and matching is performed, and the inter-pattern distance obtaining step of obtaining the inter-pattern distance is obtained by the inter-pattern distance obtaining step. A similar section search step of narrowing down the partial pattern similar to the feature pattern based on the plurality of pattern distances; and a similar section output step of outputting one or a plurality of the partial patterns narrowed down in the similar section search step. A video search method characterized by comprising: 2. A video search method for obtaining a similar section from a video to be searched by using a time-series change of a feature amount extracted from an input video as a search key, wherein the video to be searched is a video to be searched. A search target video input step of inputting a video; a standard pattern extraction step of extracting a time series of the coordinates of an object in a frame as a time series feature amount from the search target video as a standard pattern; and a standard for recording the standard pattern. A pattern storage step, a search key video input step of inputting a search key video which is a video serving as a search key, and a time series of coordinates of an object in a frame are extracted from the search key video as a feature pattern as a time series feature amount. Extracting a feature pattern from all of the partial patterns that can be selected from the standard pattern. An inter-pattern distance obtaining step of performing matching by nonlinearly expanding and contracting a feature pattern so that an inter-pattern distance obtained by a predefined inter-pattern distance function is minimized, and obtaining an inter-pattern distance; and A similar section search step of narrowing down the partial pattern similar to the feature pattern based on the plurality of pattern distances obtained by the above, and a similar section outputting one or a plurality of the partial patterns narrowed down in the similar section search step A video search method comprising an output step. 3. A video search method for obtaining a similar section from a video to be searched by using a time-series change of a feature amount extracted from an input video as a search key, wherein the search target is a video to be searched. A search target video input step of inputting a video; a standard pattern extraction step of extracting a camera motion time series as a time series feature amount from the search target video as a standard pattern; and a standard pattern storage step of recording the standard pattern. A search key video input step of inputting a search key video which is a video serving as a search key; a feature pattern extraction step of extracting a time series of camera motion as a feature pattern from the search key video as a feature pattern; A feature pattern is set in advance for all partial patterns that can be selected from the standard pattern. The feature pattern is nonlinearly expanded and contracted so as to minimize the inter-pattern distance obtained by the defined inter-pattern distance function, matching is performed, and the inter-pattern distance obtaining step of obtaining the inter-pattern distance is obtained by the inter-pattern distance obtaining step. A similar section search step of narrowing down the partial pattern similar to the feature pattern based on the plurality of pattern distances obtained, and a similar section output step of outputting one or a plurality of the partial patterns narrowed down in the similar section search step And a video search method. 4. A video search apparatus for obtaining a similar section from a video to be searched by using a time-series change in a feature amount extracted from an input video as a search key, wherein the video to be searched is a video to be searched. Search target video input means for inputting video, standard pattern extraction means for extracting a time series of frame luminance as a standard pattern from the search target video as a time series feature amount, and standard pattern storage means for recording the standard pattern Search key video input means for inputting a search key video which is a video serving as a search key; feature pattern extraction means for extracting a time series of frame luminance as a feature pattern from the search key video as a time series feature quantity; The feature pattern is defined with respect to all the partial patterns that can be selected from the standard pattern, by defining a predefined pattern distance relationship. A pattern-to- pattern distance obtaining means for obtaining a pattern-to-pattern distance by performing non-linear expansion and contraction of the feature pattern so that the pattern-to-pattern distance obtained by the number is minimized; and a plurality of patterns obtained by the pattern-to-pattern distance obtaining means. A similar section search unit that narrows down the partial pattern similar to the feature pattern based on the distance between the two, and a similar section output unit that outputs one or a plurality of the partial patterns narrowed down by the similar section search unit. A video search device characterized by the following. 5. A video search apparatus for obtaining a similar section from a video to be searched by using a time-series change of a feature amount extracted from an input video as a search key, wherein the search target is a video to be searched. Search target video input means for inputting a video; standard pattern extraction means for extracting a time series of coordinates of an object in a frame as a time series feature amount from the search target video as a standard pattern; and a standard for recording the standard pattern. Pattern storage means; search key video input means for inputting a search key video which is a video serving as a search key; extracting a time series of coordinates of an object in a frame as a feature pattern from the search key video as a time series feature amount Feature pattern extracting means, and the feature pattern is defined in advance for all partial patterns that can be selected from the standard pattern. The characteristic pattern is nonlinearly expanded and contracted so as to minimize the inter-pattern distance obtained by the inter-pattern distance function, and matching is performed, and the inter-pattern distance obtaining means for obtaining the inter-pattern distance is obtained by the inter-pattern distance obtaining means. A similar section search unit for narrowing down the partial pattern similar to the feature pattern based on a plurality of inter-pattern distances; and a similar section output unit for outputting one or a plurality of the partial patterns narrowed down by the similar section search unit. A video search device, comprising: 6. A video search apparatus for obtaining a similar section from a video to be searched by using a time-series change of a feature amount extracted from an input video as a search key, wherein the video to be searched is a video to be searched. Search target video input means for inputting a video; standard pattern extraction means for extracting a time series of camera motion as a standard pattern from the search target video as a standard pattern; standard pattern storage means for recording the standard pattern; Search key video input means for inputting a search key video as a video serving as a search key; feature pattern extraction means for extracting a time series of camera motion as a feature pattern from the search key video as a feature pattern; A feature pattern is defined for all of the partial patterns that can be selected from the standard pattern, as a predefined pattern distance. A feature pattern is nonlinearly expanded and contracted so as to minimize the inter-pattern distance obtained by the separation function, matching is performed, and an inter-pattern distance obtaining unit that obtains an inter-pattern distance is provided. A similar section search unit for narrowing down the partial patterns similar to the feature pattern based on an inter-pattern distance; and a similar section output unit for outputting one or a plurality of the partial patterns narrowed down by the similar section search unit. A video search device characterized by the above-mentioned. 7. A search target in a recording medium recording a video search program for finding a similar section from a search target video using a time-series change of a feature amount extracted from an input video as a search key. A search target video input procedure for inputting a search target video which is a video, a standard pattern extraction procedure for extracting a time series of frame luminance as a standard pattern from the search target video as a time series feature amount, a standard for recording the standard pattern A pattern storage procedure, a search key video input procedure for inputting a search key video which is a video serving as a search key, a feature pattern extraction procedure for extracting a time series of frame luminance as a feature pattern from the search key video as a time series feature quantity The feature pattern is defined with respect to all the partial patterns that can be selected from the standard pattern. A pattern obtained by the pattern distance obtaining procedure for obtaining the pattern distance by performing matching by nonlinearly expanding and contracting the characteristic pattern so that the pattern distance obtained by the inter-turn distance function is minimized, A similar section search procedure for narrowing down the partial pattern similar to the feature pattern based on the inter-pattern distance, and a similar section output procedure for outputting one or a plurality of the partial patterns narrowed down in the similar section search procedure. A recording medium on which a video search program is recorded. 8. A recording medium on which a video search program for searching for a similar section from a video to be searched is recorded using a time-series change of a feature amount extracted from the input video as a search key, to be a search target. A search target video input procedure for inputting a search target video which is a video, a standard pattern extraction procedure for extracting a time series of coordinates of an object in a frame as a standard pattern from the search target video as a time series feature amount, A standard pattern storage procedure to be recorded, a search key video input procedure for inputting a search key video serving as a search key video, and a time series of coordinates of an object in a frame as a feature pattern as a time series feature amount from the search key video. A feature pattern extraction procedure to be extracted; the feature pattern is extracted for all partial patterns that can be selected from the standard pattern. The pattern distance is obtained by performing non-linear expansion and contraction of the feature pattern so that the pattern distance obtained by the previously defined pattern distance function is minimized, and the pattern distance is obtained. A similar section search procedure for narrowing down the partial patterns similar to the feature pattern based on the obtained plurality of inter-pattern distances, and a similar section output procedure for outputting one or a plurality of the partial patterns narrowed down in the similar section search procedure Recording medium for recording a video search program for executing the program. 9. A recording medium on which a video search program for obtaining a similar section from a video to be searched is recorded by using a time-series change of a feature amount extracted from an input video as a search key, to be a search target. A search target video input procedure for inputting a search target video as a video, a standard pattern extraction procedure for extracting a time series of camera motion as a time series feature amount from the search target video as a standard pattern, a standard pattern for recording the standard pattern A storage key procedure, a search key video input procedure for inputting a search key video which is a video serving as a search key, a feature pattern extraction procedure for extracting a time sequence of camera motion as a feature pattern from the search key video as a feature pattern, A feature pattern is defined in advance for all partial patterns that can be selected from the standard pattern. The characteristic pattern is nonlinearly expanded and contracted so that the inter-pattern distance obtained by the inter-pattern distance function is minimized, matching is performed, and the inter-pattern distance obtaining procedure for obtaining the inter-pattern distance is obtained by the inter-pattern distance obtaining procedure. A similar section search procedure for narrowing down the partial patterns similar to the feature pattern based on a plurality of pattern distances, and a similar section output procedure for outputting one or a plurality of the partial patterns narrowed down in the similar section search procedure are executed. Recording medium on which a video search program for recording is recorded.