JP2016014990A - Moving image search method, moving image search device, and program thereof - Google Patents

Abstract

PROBLEM TO BE SOLVED: To easily perform search or grouping with a moving image itself as a query with high accuracy by more suppressing calculation costs than a conventional manner.SOLUTION: First featured value extraction means 12 or second featured value extraction means 22 respectively extracts the featured values of a query moving image and an object moving image. Query moving image representative frame selection means 13 or object moving image representative frame selection means 23 clusters each frame from a relation between featured values within a range of time width limited by a time window, and allows the time window to slide on a time axis as for the query moving image and the object moving image. Thus, it is possible to time-sequentially acquire the representative frame for each scene. Furthermore, similarity calculation means 31 or similar moving image display control means 32 obtains similarity between the query moving image and the object moving image from inter-representative similarity between the query moving image and the object moving image, and searches a moving image similar to the query moving image.

Description

  The present invention relates to a moving image search method, a moving image search device, and a program thereof.

A huge amount of moving image data is accumulated on the Internet. A text-based search method is known as a frequently used method for searching these moving images. This text-based search method searches for a desired moving image by associating appropriate text information with each moving image and performing a text search. However, this method has the following problems.
(A) The association (labeling) of the moving image and the text information needs to be performed manually, which is expensive.
(B) Since an inappropriate label with poor versatility is attached, the accuracy and efficiency of search may be reduced.

  As a method for solving the above problem, a content-based search using the image content (content) itself as a query is expected.

  As a content-based search method, the query image and the search target image can be obtained by combining information about the entire image such as brightness change and complexity of the entire image, complexity of the edge amount, simple composition information using the luminance distribution, or a combination thereof. There has been proposed a method for calculating the degree of similarity (see, for example, Patent Document 1). Further, by dividing a plurality of search target images into element images of a predetermined size, selecting a representative element image from the divided element images, and using a search reference image drawn using the representative element image A method for searching for an image has also been proposed (for example, see Patent Document 2).

  However, these proposed methods search still images using still images as queries, and do not consider a method for searching for moving images as queries.

JP 2001-56820 A JP 2002-140331 A

  As described above, in the prior art, there is only a disclosure about a method using a text base or a still image as a query, and what is disclosed about a moving image search based on a moving image content using a moving image as a query is disclosed. There was no consideration. An object of the present invention is to provide a moving image search method, a moving image search apparatus, and a program thereof that can perform a search using a moving image itself as a query with high accuracy while keeping calculation cost low.

  The present invention provides a means by which a correlation between a large number of moving images, that is, a phase can be calculated numerically. As a result, it is possible to label big data composed of moving images by machine learning, and to perform searches and groupings using the moving images themselves as queries. At this time, the label is obtained by adding the number of representative frames, the number, and the number of governing frames to the header. Such formatting is easy and has the path to standardization.

That is, the present invention is a moving image search method by a moving image search apparatus for calculating a similarity of a target moving image with respect to a query moving image and searching for a moving image similar to the query moving image,
A first step of extracting a feature amount from each frame of the query moving image and the target moving image;
For the query moving image and the target moving image, the frames are clustered from the relationship between the feature amounts within a time width limited by the time window, and the time window is slid on the time axis. A second step of acquiring a representative frame in time series for each scene;
From the representative frame similarity between the representative frame in the query video and the representative frame in the target video, the similarity between the query video and the target video is obtained, And a third step of searching for the moving image similar to the query moving image.

In the moving image search method, in the third step,
The number of frames E ^A _i represented by the i th representative frame of the query image, the number of frames E ^B _j represented by the j th representative frame of the target moving image, and the i th representative frame of the query image Obtaining the inter-representative frame similarity s (i, j) with the j-th representative frame of the target moving image,
Set gap penalty g,
When the number of the representative frames in the query moving image is m and the number of the representative frames in the target moving image is n, each component f (i, j) of the matrix of (m + 1) × (n + 1) about,
Calculate each component f (0, j) of the row of i = 0 based on the following equation 1;

  Calculate each component f (i, 0) in the column of j = 0 based on the following formula 2;

When the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i, j) other than i = 0 rows and j = 0 columns are used. j) is calculated based on the following equation 3,

  The similarity between the query moving image and the target moving image is calculated using the numerical value of the last row and the last column of the matrix.

Instead, in the third step,
The number of frames E ^A _i represented by the i th representative frame of the query image, the number of frames E ^B _j represented by the j th representative frame of the target moving image, and the i th representative frame of the query image Obtaining the inter-representative frame similarity s (i, j) with the j-th representative frame of the target moving image,
Set gap penalty g,
When the number of the representative frames in the query moving image is m and the number of the representative frames in the target moving image is n, each component f (i, j) of the matrix of (m + 1) × (n + 1) about,
Each component f (0, j) in the row with i = 0 and each component f (i, 0) in the column with j = 0 are all set to 0,
When the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i, j) other than i = 0 rows and j = 0 columns are used. j) is calculated based on the following equation 4,

  The similarity between the query moving image and the target moving image may be calculated using the maximum value among the components of the matrix.

The present invention is also a moving image search device for calculating a similarity of a target moving image to be searched with respect to a query moving image and searching for a moving image similar to the query moving image,
Feature amount extraction means for extracting a feature amount from each frame of the query moving image and the target moving image;
For the query moving image and the target moving image, the frames are clustered from the relationship between the feature amounts within a time width limited by the time window, and the time window is slid on the time axis. Representative frame selection means for acquiring representative frames in time series for each scene;
From the representative frame similarity between the representative frame in the query video and the representative frame in the target video, the similarity between the query video and the target video is obtained, Moving image search means for searching for the moving image similar to the query moving image.

In the moving image search apparatus, the moving image search means includes:
The number of frames E ^A _i represented by the i th representative frame of the query image, the number of frames E ^B _j represented by the j th representative frame of the target moving image, and the i th representative frame of the query image Obtaining the inter-representative frame similarity s (i, j) with the j-th representative frame of the target moving image,
Set gap penalty g,
When the number of the representative frames in the query moving image is m and the number of the representative frames in the target moving image is n, each component f (i, j) of the matrix of (m + 1) × (n + 1) about,
Calculate each component f (0, j) in the row of i = 0 based on the following equation 5:

  Calculate each component f (i, 0) in the column of j = 0 based on the following equation 6:

When the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i, j) other than i = 0 rows and j = 0 columns are used. j) is calculated based on the following equation 7,

  The similarity between the query moving image and the target moving image is calculated using the numerical value of the last row and the last column of the matrix.

Instead, the moving image search means
The number of frames E ^A _i represented by the i th representative frame of the query image, the number of frames E ^B _j represented by the j th representative frame of the target moving image, and the i th representative frame of the query image Obtaining the inter-representative frame similarity s (i, j) with the j-th representative frame of the target moving image,
Set gap penalty g,
When the number of the representative frames in the query moving image is m and the number of the representative frames in the target moving image is n, each component f (i, j) of the matrix of (m + 1) × (n + 1) about,
Each component f (0, j) in the row with i = 0 and each component f (i, 0) in the column with j = 0 are all set to 0,
When the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i, j) other than i = 0 rows and j = 0 columns are used. j) is calculated based on the following equation 8,

  It is good also as a structure which calculates the said similarity between the said query moving image and the said target moving image using the maximum value in each component of the said matrix.

  With the above-described moving image search method, moving image search apparatus, and program thereof of the present invention, a search using a moving image as a query can be performed with high accuracy while keeping the calculation cost low.

In one Example of this invention, it is a block diagram which shows the system configuration | structure of a moving image search device. It is explanatory drawing of the operation | movement flow processed with the processing apparatus of FIG. 1 same as the above. It is explanatory drawing which shows the difference between the clustering which considered the time series information applied in one Example of this invention, and the clustering which does not consider the time series information of a prior art. 6 is a flowchart showing a representative frame selection algorithm by an affinity propagation method (TBAP, Time-Bound Affinity Propagation) using a time window in an embodiment of the present invention. It is explanatory drawing which shows the mode of message exchange in one Example of this invention, and a prior art. FIG. 4 is an explanatory diagram showing a message exchange link matrix in an embodiment of the present invention. FIG. 4 is an explanatory diagram showing, on the time axis, time windows in TBAP and time blocks in the improved k-means method and harmonic competition method. It is a flowchart which shows the similarity calculation algorithm by M distance same as the above. It is explanatory drawing showing the production | generation process of the original moving image data used in experiment. It is explanatory drawing which shows the structure of the moving image data of FIG. This is a plot of each of the five Gaussian clusters divided into two in the time direction and made into 10 groups. This figure was used to examine the appearance and calculation speed of representative points (typical still images) reflecting temporal characteristics. is there. Is a diagram showing the distance of each representative still image of the moving image v _A and moving image v _B as matrix. It is a figure which shows an example of the table for global alignment obtained by experiment. It is a figure which shows an example of the table for local alignment obtained by experiment. 14 corresponds to the global alignment table of FIG. 13 and is a diagram in which a portion where calculation has been omitted is blacked out. It is a graph which shows the precision-recall rate curve in the moving image search obtained by experiment.

  Hereinafter, preferred embodiments of a moving image search method and an apparatus for realizing the same according to the present invention will be described in detail with reference to the accompanying drawings.

  FIG. 1 schematically shows a preferred example of the system configuration of the moving image search apparatus in the present embodiment. In the figure, 1 is a database that stores and saves a set of moving images, 2 is a processing device such as a computer that searches for similar images, 3 is a moving image used for searching and a moving image to be searched, and search results A display 4 displays input means such as a mouse and a keyboard. The database 1 is connected to the processing device 2 in a readable state. The processing device 2 can display the moving images stored in the database 1 on a display 3 as display means as necessary. The database 1 may be a storage medium (such as a hard disk) that is built in or externally attached to the processing device 2, or may be constructed on a server that is connected to the processing device 2 via communication means. Further, the query image and the search target image can be stored in separate databases, and the form is not particularly limited. Further, the processing device 2 is connected to the input means 4 and can appropriately accept input from the user.

  The processing device 2 is installed with application software for searching for similar moving images. The processing device 2 executes the installed program to capture a moving image from the database 1, calculate and analyze the feature amount of the captured moving image, and then analyze a moving image similar to the query moving image. A process for searching from the target moving image is performed. Moreover, by installing application software, it can function as each means as shown below.

  The processing device 2 includes a query moving image capturing unit 11, a first feature quantity extracting unit 12, and a query moving image representative frame selecting unit 13 as functional units that process the query moving image. The query moving image capturing means 11 is for capturing a query moving image selected by the user by the input means 4 from the moving images stored in the database 1. The first feature amount extraction unit 12 is for extracting the feature amount of the query moving image captured by the query moving image capturing unit 11. The query moving image representative frame selection unit 13 is for selecting one or more representative frames in the query moving image based on the feature amount of the query moving image extracted by the first feature amount extraction unit 12. .

  The processing device 2 includes a target moving image capturing unit 21, a second feature amount extracting unit 22, and a target moving image representative frame selection unit 23 as functional units that perform processing of the target moving image. The target moving image capturing means 21 captures a target moving image to be searched from among the moving images stored in the database 1. The second feature amount extraction unit 22 is for extracting the feature amount of the target moving image captured by the target moving image capturing unit 21. The target moving image representative frame selecting unit 23 is for selecting one or more representative frames in the target moving image based on the feature amount of the query moving image extracted by the second feature amount extracting unit 22. .

  In addition, the processing device 2 includes a similarity calculation unit 31 and a similar moving image display control unit 32 as means for searching for a target moving image similar to the query moving image. The similarity calculation unit 31 compares the feature amount of each representative frame in the query moving image with the feature amount of each representative frame in the target moving image, and calculates the similarity. The similar moving image display control unit 32 displays one or more target moving images on the display 3 in descending order of the similarity calculated by the similarity calculating unit 31.

  FIG. 2 shows a processing outline of the processing apparatus 2 of the present invention. In the figure, the left route represents a query moving image processing step, and the right route represents a target moving image processing step. With the processing in FIG. 2, finally, the similarity of the target moving image to the query moving image is calculated.

  The processing steps for the query moving image of the left route in FIG. 2 will be described. In step S110, a query moving image is fetched from the database 1. In step S120, the feature amount of the query moving image is extracted. As the feature amount, a color structure descriptor (CSD), which is one of the image feature amounts proposed in MPEG-7, can be used. In step S130, a representative frame of the query moving image is determined as a typical still image. At this time, the representative frame is determined by using a method that takes into consideration an element of the elapsed time of the moving image, such as a time-bound affinity propagation method (TBAP). Although depending on the number of frames of the query moving image, a plurality of representative frames are usually selected, and the feature amount set of each typical still image corresponding to the selected representative frame is set as the feature amount of the query moving image. .

  The processing steps for the target moving image on the right path in FIG. 2 are performed in the same procedure as the processing steps for the query moving image. That is, the target moving image is captured from the database 1 in step S140. In step S150, the feature amount of the target moving image is extracted. The CSD described above can be used as the feature amount. In step S160, a representative frame is determined as a typical still image. At this time, the representative frame is determined using a method that takes into account the elements of the elapsed time of the moving image, such as the above-described TBAP. Although depending on the number of frames of the target moving image, a plurality of representative frames are usually selected, and a set of feature amounts of each typical still image corresponding to the selected representative frame is set as a feature amount of the target moving image. .

  Note that the target moving image representative frame selection means 23 can apply a k-means method in which a time block is introduced as an alternative technique of TBAP, or a harmonic competition in which a time block, which is a generalization thereof, is introduced. The harmonic competition method is described in Reference 1 and the like, but the improved k-means method and harmonic competition method proposed in the present invention will be described in detail later.

  Reference 1: Matsuyama, Yasuo, “Harmonic Competition: A Self-Organizing Multiple Criteria Optimization”, IEEE Transactions on Neural Networks, Vol.7, No.3, pp.652-668, MAY 1996

  In this way, when the representative frames (typical still images) are selected for the query moving image and the target moving image, the similarity calculation processing in step S170 is performed. Since the number of typical still images here depends on each moving image, the similarity between the query moving image and the target moving image is calculated by a weighted M distance that allows gap insertion. The M distance will be described in detail later. In step S180, based on the similarity score calculated in step S170, a target moving image with a high similarity is retrieved and displayed on the display 3.

  In the processing steps described above, the extraction of the feature amount in steps S120 and S150 is stage 1, the representative frame selection in steps S130 and S160 is stage 2, and the similarity calculation in step S170 is stage 3. Hereinafter, each of the steps 1 to 3 will be described in detail.

Step 1: Extracting Feature Amounts for Each Frame In Step 1, feature amounts of each frame included in a query moving image or a representative moving image (hereinafter simply referred to as a moving image) are extracted. The feature amount extracted here is expressed as a vector {x _t } ⁿ _{t = 1} in consideration of time series. For example, so that the processing by the application software used in the similar image search can handle a moving image having color information, the vector is expressed by the above-described MPEG-7 CSD, and all the vectors are normalized with the CSD histogram. can do.

However, the feature amount of each frame of the moving image is not limited to that using CSD, and the feature amount may be any vector amount as long as the following normalization condition is satisfied.
-Normalization conditions (i) Each vector component is non-negative.
(Ii) The sum of all vector components is set to 1.0.
This is obtained by the following procedure.
(A) Each frame of the moving image is changed to a vector amount representing the feature (feature amount extraction).
(B) A method that can normalize each vector is employed so as to ensure a similarity comparison method and versatility when it is realized as software.

  The procedure (b) is always possible by using substantially the minimum value and sum of each vector. CSD is merely an example of the feature vector in the procedure (a), and a simpler one that covers only the entire image frame is a histogram.

  CSD is a simple feature amount, but it is preferable because good results can be obtained. Moreover, although the amount of calculation increases instead of CSD, it is also possible to use a feature amount by another method. For example, SIFT (Scale-Invariant Feature Transform), SURF (Speeded Up Robust Features), FREAK (Fast Retina Keypoint), bag of visual words, etc. can be used for the feature amount of each frame of the moving image. It is also possible to combine feature quantities other than CSD and feature quantities including CSD.

  For example, when {CSD, FREAK, bag of visual words, SIFT,...} Is described as a group of individual normalized feature amounts, and the individual normalized feature amounts are expressed as NormalizedFeatureVector (i), a moving image frame As the feature quantity, a composite feature quantity vector CompositeFeatureVector defined in the following Equation 9 can also be used.

However, the combined feature vector CompositeFeatureVector satisfies the normalization conditions: w _i ≧ 0 and Σ ^N _{i = 0} w _i = 1 in the above equation. The above formula 9 is merely an example of obtaining a composite feature vector CompositeFeatureVector. For example, a product obtained by multiplying feature amounts can be used as a composite feature vector CompositeFeatureVector. Therefore, the composite feature quantity vector CompositeFeatureVector is obtained by the following general formula (10). This is a mathematical expression of the expression that what is finally normalized by combining several individual feature quantities FeatureVector (i) becomes a composite feature quantity vector CompositeFeatureVector.

Stage 2: Selection of representative frames to keep time series This stage is performed after extracting normalized features using various techniques in Step 1 for each frame of the moving image. Here, the processing device 2 clusters each frame in the moving image based on the feature amount, and selects a frame representing each cluster. A frame representing each cluster is referred to as a typical still image, but time series information must be added to the selection of a typical still image. Before describing the specific algorithm at this stage, a few points to note.

FIG. 3 is a diagram for explaining a difference in clustering between the present embodiment and a normal affinity propagation method (AP). The time-series data in the upper part of the figure represents n = 10 time-series feature vectors {x _t } ¹⁰ _{t = 1} from time t = 1 to time t = 10 extracted in stage 1. Each box here represents a frame at each time t. For example, a number 1 is assigned to a frame at time t = 1, and a number 5 is assigned to a frame at time t = 5. Also, the frames drawn with the same gradation in the figure represent similar frames (for example, one scene in a moving image) and belong to the same class. In the illustrated example, there are three types of sets of similar frames: {1,2,10} class, {3,4,5} class, {6,7,8,9} class.

When these frames are clustered by feature amount, when the normal affinity propagation method (AP) is used, for example, frames {2, 4, 7} Elected. However, this does not take time series information into consideration, and is not appropriate as a label for searching for moving images. By correctly considering the time series, the typical still image is selected as {2, 4, 7, 10} as shown in the lower right part of the figure. Time-constrained affinity propagation method (TBAP) that considers the elapsed time of moving images, and improved k-means method or harmonic competition method that approximates it allow clustering considering such time series. . That is, in the example of FIG. 3, when the time-constrained affinity propagation method is applied, the typical still image is correctly {(1, 2 , 0) (1, 4 , 1), (1, 7 , 2), (0, 10 , 0)}. Such clustering is realized not only by TBAP but also by the restriction of the time window by the improved k-means method and harmonic competition method.

  Note that the number of frames of these typical still images varies according to the length of the moving image and the content. Thus, each typical still image includes a responsible frame on its left and right in time order.

  Hereinafter, the TBAP algorithm, which is one of the algorithms for selecting a typical still image that keeps time series, will be described in detail with reference to the flowchart of FIG.

Step S210: Calculation of Similarity Here, n time-series feature vectors {x _t } ⁿ _{t = 1} extracted in stage ₁ are given for a moving image frame from time t = 1 to time t = n. . As described above, each feature vector {x _t } ⁿ _{t = 1} is a normalized CSD histogram with a total of one. From the feature vectors _{x i} of the time t = i, define the time t = j Similarity measure _{s (x} i, _{x j)} representing the relationship between the feature vector _{x j} of the as s (i, j). Then, when and only when the feature vector x _i is more similar to the feature vector x _k at time t = k than the feature vector x _j , s (k, i)> s (k, j) is satisfied. It shall have properties.

  In the present embodiment, the similarity measure s (i, j) calculated by the following equation 11 is used.

  However, bar (D) (hereinafter, the symbol D with an overline as in the first term on the right side of Expression 11 is expressed as bar (D) in the text) is input by the input means 4, for example. Is a constant parameter that can be set.

  As long as the similarity is set according to the rule that “the larger the value, the greater the relationship, and the smaller the value, the smaller the relationship”, any value may be used as long as the similarity is set. The method of selecting bar (D) does not affect the result of TBAP, so it is set to 0 here. However, this parameter is an important factor in comparing moving images, and can take a value other than 0.

Step S220: Initializing the matrix A Here, a matrix A = [a _ij ] having an initial value of zero matrix is prepared (a _ij ← 0). This matrix A is a matrix representing availability. The availability is a message sent from the data point j of the typical still image candidate to the data point i and is a value representing how appropriate it is to select the data point i as the typical still image of the data point j.

Step S230: Calculate (or update) the matrix R using the matrix A
Here, first, the length of the sliding time window is set to W = 2ω−1 so that its center is located at the diagonal component, and then the feature vector x is considered in consideration of the time series in the time window. _{i, x} j, to select the _{x k.}

Next, the component r _{ij of the} matrix R representing the responsibility is calculated and updated using the availability matrix A described above. Responsibility is a message sent from data point i to data point j of a typical still image candidate, and is a value representing how appropriate data point i is as a typical still image of data point j. In the calculation of the responsibility matrix R and the calculation of the availability matrix A, which will be described later, the data points i and j are set within the range of the following equation (12). In other words, in TBAP, the limit shown in Equation 12 is set in the range for message exchange.

  The responsibility matrix R is usually symmetric and is updated using the matrix A as shown in Equation 13.

In Equation 13, ρ _ij is a propagation value of responsibility between the data point i and the data point j. Further, λε (0,1) is a damping coefficient as a design parameter, and by using this, the convergence in step S250 described later can be delayed, and a stable result can be obtained. The initial value of the matrix R is also a zero matrix, but if the damping coefficient λ is 0, for example, the response propagation value ρ _ij is updated as it is as the value of the matrix R.

Step S240: Calculate Matrix A Here, the data points i and j are limited to the range indicated by Equation 12, and the component a _ij of the availability matrix A is updated using the following Equation 14.

In Expression 14, α _ij is a propagation value of availability between the data point i and the data point j.

Step S250: Determine whether or not the sum of the matrix A and the matrix R has converged. The component a _{ij of the} matrix A calculated as described above and the component r _{ij of the} matrix R are added, and the value a _ij + r _ij Steps S230 and S240 are repeated until the convergence criterion is satisfied. On the other hand, when the value of a _ij + r _ij satisfies the convergence criterion, the process proceeds to the next step S260.

Step S260: Representative Frame Selection Here, the index defined in the following Equation 15 is adopted as the index of the typical still image.

That is, the still image at the data point where the value of a _ij + r _ij is the maximum is adopted as the typical still image. For example, the data point i belongs to a cluster centered on the data point j having the maximum value of a _ij + r _ij . A set of typical still images finally selected as representative frames is found by collecting such indexes.

  In the series of steps S230 to S260, ω necessary for setting the time window is a parameter that limits the range of message exchange when the matrix A and the matrix R are calculated. FIG. 5 shows how messages are exchanged under this restriction. In the figure, “AP” in the upper part indicates a range of message exchange by the affinity propagation method as a conventional technique. The lower “TBAP” indicates the range of message exchange by the time-constrained affinity propagation method in this embodiment. Here, it is assumed that the same frames as described in FIG. 3 are arranged in time series.

  In the prior art, messages are exchanged for all data points. In this embodiment, messages are exchanged for neighboring data points limited by a time window. Specifically, in the example of “AP” shown in FIG. 5, data exchange is performed over the entire range from data point j = 1 to j = 10 with data point i = 5 as the center. On the other hand, in the example of “TBAP” in the figure, the parameter ω is set to 4 and the message exchange is performed in the range of the time window 2ω-1 = 7. Therefore, the range of message exchange is limited to the range of data points j = 2 to j = 7 with data point i = 5 as the center.

  FIG. 6 shows a link matrix for message exchange to which the TBAP of this embodiment is applied. Again, the parameter ω = 4 is set, and when the data point i is selected from 1 to 10, the data point j with which the message is exchanged is shown.

  As a characteristic of a normal AP, only data points for which messages have been exchanged are finally selected as typical still image candidates. The same can be said for the TBAP of this embodiment. In the TBAP of this embodiment, the range for exchanging messages is limited in consideration of time series. As a result, data points that are distant in time series without message exchange (for example, time t = 10 shown in FIG. 3). ) Can be selected as one of the representative frames by clustering.

Regarding the adoption of a typical still image in TBAP, the same typical still image can be taken even if the time window is exceeded for consecutive similar frames. Specifically, it is assumed that the typical still image e _i for the i-th frame is determined. At this time, it is determined that the feature vectors from the k-th frame to the (i−1) -th frame before the i-th frame are similar using a threshold or the like, and the typical still image e _k for the k-th frame and the If it is determined that the typical still image e _i for the i frame is also similar, the typical still image e _k can be used as it is without generating a new typical still image e _i . As a result, the performance of the present invention can be improved.

As described above, in the present embodiment, the similar moving image search processing device 2 executes the processing steps based on the TBAP, so that a set of typical still images considering time series is obtained from the query moving image and the target moving image, respectively. Can be extracted. Then, the extracted feature amount of the representative frame is determined as the feature amount of the moving image, and this stage is finished. In particular, the TBAP employed in the present embodiment provides a time window that slides with the selected data point, so that the number of message exchanges is limited, and the complexity of message transmission is O (ωn). On the other hand, the complexity of a normal AP is O (n ² ). In other words, since the calculation cost of the AP is proportional to the square of the number of data points, there is a problem that a calculation time is required when the number of data points increases. On the other hand, in the present embodiment, generally, ω <n, so that TBAP can keep the calculation cost lower than AP. In addition, the algorithm of TBAP is faster than AP.

  Next, an improved k-means method and harmonic competition method, which are alternative methods of TBAP, will be described with reference to FIG. The left side of the figure shows a time window W that slides on the time axis in TBAP, and the right side of the figure shows a time window W that slides on the time axis in the improved k-means method and harmonic competition method. It is shown.

  TBAP uses a series of image frames in a time window W that slides so as to overlap along a time axis as a calculation target. On the other hand, in the improved k-means and harmonic competition, which are alternative techniques, image frames in the time window W without overlap are targeted for calculation. In other words, in TBAP, the shift width of the time window W is smaller than the frame length of the time window W, and the time window W slides by one or more frames, whereas in the improved k-means and harmonic competition, the time window W The shift width matches the frame length of the time window W, and the time window W slides in units of the time window W.

  For example, when the improved k-mean or harmonic competition is used in the procedure of Step 2, the image frame is divided into time windows W along the time axis, and clustering is performed in the divided time windows W. The representative point vector obtained here does not correspond to the original image itself, but is a feature vector of a similar image (artificial image) generated by calculation based on k-mean or harmonic competition. Therefore, a two-step calculation procedure is required in which a frame having features most similar to the representative point vector is selected as a typical still image. The typical still image obtained by this two-stage calculation is approximate to the typical still image of TBAP.

  In addition, although the flowchart of FIG. 4 mentioned above has shown the processing procedure of TBAP using the sliding time window W, the length of the time window W is set to 2ω-1 also in k-mean and harmonic competition. A similar processing procedure can be applied.

  In this way, the concept of the time window W in TBAP is applied to k-mean and harmonic competition, and the time window W is slid from the time axis W so that it does not overlap along the time axis. If a point vector is acquired, a frame having a feature closest to the representative point vector can be selected as a typical still image.

  Regarding the normalization of data and the distance measure, the Similarity measure s (i, j) may be any as long as the algorithm converges. If the parameter λ is set appropriately, the form of the Similarity measure s (i, j) in Equation 3 results in convergence of the algorithm.

Since each feature vector _xt is normalized to have only non-negative components where the sum of each component is 1, the options for bar (D) are as follows:
(A) Average value of all data distances: This is allowed only when the data size is small.
(B) Either √2, √ ((d−2) / (2d)), or √ (1- (1 / d)): where d represents the dimension of the feature vector x _t existing in the simplex . √2 is the edge of the simplex, √ ((d−2) / (2d)) ≈1 / √2 is the radius of the inner sphere, and √ (1− (1 / d)) ≈1 is the outer sphere Represents the radius. Note that ≈ means an approximate symbol, and the approximation is effective when d is sufficiently large.

  For example, the above-mentioned CSD uses HSV (Hue-Saturation-Brightness) color space expression, and the ratio of each value of H, S, V is quantized to H: S: V = 12: 8: 8. Is preferred. In this case, each image is expressed by 12 × 8 × 8 = 768 colors, and the feature amount by CSD is a 768-dimensional histogram. Therefore, the CSD binary size is d = 768 and the value representing the radius of the outer sphere is bar. Used as (D).

Stage 3: Calculation of similarity by analysis between moving pictures In stage 3, different moving pictures having different sets of typical still pictures are compared. In order to search between moving images based on content, it is necessary to compare the similarity between the query moving image and the target moving image. Here, based on the information in the moving image analyzed in Step 1 to Step 2, comparison between different moving images is performed by one of the two methods described below. In this embodiment, the comparison target is a moving image, but it is not limited to this as long as it is time-series data having an exemplar such as a representative frame.

(1) Comparison of Similarity Using M Distance for Obtaining Global Alignment In this embodiment, a distance called M distance is used as a scale for comparing similarity. The M distance for global alignment is a generalization of the Levenshtein distance (L-distance) for measuring the similarity of character strings and the Needleman-Wunsch algorithm for obtaining global alignment in bioinformatics. Accordingly, the M distance for global alignment is included as a special case of the Levenshtein distance or the Needleman-Wunsch algorithm.

  Hereinafter, an algorithm using the M distance for global alignment will be described in detail with reference to the flowchart of FIG.

Step S310: Prepare typical still images of the query moving image and the target moving image For the moving image v _A corresponding to the query moving image, the set of typical still images {e ^A _i } and the typical still image possessed by the typical still image. ^A set {E ^A _i } of frames (i = 1, 2,...) Is given. _A similar set {e ^B _j }, {E ^B _j } (j = 1, 2,...) Is also given to the moving image v _B corresponding to the target moving image to be compared with the moving image v _A. It is done. Here, the Similarity measure s (i, j) in Equation 11 is selected as the similarity between representative frames.

Step S320: Create a table and follow the route according to the following dynamic programming procedure.
_A matrix of (m + 1) × (n + 1) is created as a global alignment table, where m is the number of typical still images of the moving image v _A and n is the number of typical still images of the moving image v _B. Each component f (i, j) of the matrix is calculated by the following procedure by dynamic programming.

  First, in step S321, a gap penalty g set as a design parameter is selected. By introducing this gap penalty g, even if the number m of the typical still images of the query moving image and the number n of the typical still images of the target moving image are different from each other, Similarity can be determined correctly.

  In the next step S322, for the row of {i = 0} and the column of {j = 0}, the matrix constituting the table so that the value decreases stepwise by multiplying the gap g by the total number of frames. Calculate each component of. Specifically, the row of {i = 0} calculates the matrix component f (0, j) based on the following equation (16).

  For the column of {j = 0}, the matrix component f (i, 0) is calculated based on the following equation (17).

  Further, in step S323, the remaining matrix components f (i, j) other than the row of {i = 0} and the column of {j = 0} are started from the position of (i, j) = (1,1). The calculation is based on the following equation (18).

  Then, an arrow is drawn toward the component that gives the maximum value. This calculation is continued until all matrix components are calculated. Here, r (i, j) represents a weight reflecting the ownership of the typical still image, and the value is calculated based on the following equation 19, for example.

  As shown in Equation 18, the matrix component f (i, j) here is sequentially generated in the order of increasing number of rows or columns. Then, the matrix component f (i, j) of i row and j column passes through (i-1) row j column and reaches i row j column, i row j through i row (j-1) column. The route with the highest cost is selected as the optimum route from the route to the column and the route to the i row and j column via the (i-1) row (j-1) column, and the value at that time is the value of the matrix It is determined sequentially as a component.

Step S330: Determination of global alignment After the calculation of all matrix components constituting the table is completed, the global alignment path is determined by following the arrows from the last row and last column components of the matrix f (i, j). Can be obtained.

Step S340: Calculation of similarity The similarity u (A, B) between the moving image v _A and the moving image v _B is calculated based on the following equation (20).

However, h (x) is a positive increase function, and f _last is a numerical value of the last row and last column of the matrix. W is an averaging function. The averaging function can be, for example, an arithmetic average of Σ _i E _i ^A and Σ _i E _i ^B.

(2) Comparison of Similarity Applying M Distance for Obtaining Local Alignment When the moving images to be compared are greatly different from each other, the above-described global alignment is deviated from human senses. In such a case, local alignment can be used. Local alignment is useful when the sequences are not similar overall and you want to find partial similarities. The algorithm described below is an adaptation of the above global alignment method to local alignment, and uses M distance for local alignment as a measure of similarity. This M distance for local alignment is a generalization of the Smith-Waterman algorithm for obtaining local alignment in bioinformatics. Therefore, the M distance for local alignment applied in the present embodiment includes the Smith-Waterman algorithm as a special case.

  Hereinafter, an algorithm using the M distance for local alignment will be described in detail with reference to the flowchart of FIG. However, since there are many procedures that overlap with the already described M distance for global alignment, only the differences are described.

Step S310: Prepare typical still images of the query moving image and the target moving image This is the same processing procedure as the M distance for global alignment.

Step S320: Create a table and follow the route according to the following dynamic programming procedure.
_A matrix of (m + 1) × (n + 1) is created as a local alignment table where m is the number of typical still images of the moving image v _A and n is the number of typical still images of the moving image v _B. Each component of the matrix is calculated by the following procedure by dynamic programming.

  First, in step S321, a gap penalty g set as a design parameter is selected. This is the same processing procedure as the M distance for global alignment.

  In the next step S322, all components are set to 0 for the row of {i = 0} and the column of {j = 0}.

  Further, in step S323, the remaining matrix components f (i, j) other than the row of {i = 0} and the column of {j = 0} are started from the position of (i, j) = (1,1). , Based on the following equation (21).

  Then, an arrow is drawn toward the component that gives the maximum value that is not zero. On the right side of Equation 21, unlike the Equation 18, the leftmost component in the max symbol is 0. Thus, when the score value becomes negative, the value can be reset to 0 and the alignment can be newly started.

Step S330: Determination of local alignment After calculation of all matrix components constituting the table is completed, tracing of the local alignment is performed by tracing from the component of the maximum value f _{max in} the matrix f (i, j) based on the arrow. A route can be obtained.

Step S340: Calculation of Similarity Using the same processing procedure as the M distance for global alignment, the similarity u (A, B) between the moving image v _A and the moving image v _B is calculated based on Equation 20.

The similar moving image search processing device 2 executes the above steps 1 to 3 to calculate the similarity u (A, B) of each moving image v _B to the moving image v _A. Thereby, a similar moving image similar to the query moving image can be searched from the target moving image.

  Note that the TBAP used in stage 2 described above may use an AP that is not time-constrained in combination with stage 3. As a clustering method for use in the evaluation of similarity, it is possible to use an existing harmonic competition or an existing k-means method in addition to AP.

  Next, the details and results of the experiment using the moving image retrieval apparatus will be described.

  First, as for the experimental data, since the end user of the search is a human, the final determination of the similarity is strongly dependent on the sensitivity of the human. Therefore, it is desirable that the determination of similarity is not dependent on the subject as much as possible. However, with a simple set, it would be too easy to judge even with a plain device, so a data set that satisfies the following conditions was prepared in the experiment.

・ The original video data is not labeled.
・ The precision and recall in the search can be automatically judged.
It is assumed that each moving image has information that captures the time change of the scene so that the time-dependent property as shown in the lower right of FIG. 3 can be determined.

  FIG. 9 shows the generation process of the original moving image data. The group A moving image represents a “bird's eye view”, and the group B moving image represents a “bird”. In the experiment, 20 animation classes are created from these groups A and B (see FIG. 10). Since each class 1 to 20 constitutes 21 moving images, a total of 420 different test videos were used.

・ Preliminary experiment
Since the convergence of the AP algorithm depends on the data, it is necessary to confirm the range of the parameter λ in the equations 13 and 14. As a set of trial data, five groups of Gaussian clusters were generated, and further divided into two groups for each time direction to form ten groups. FIG. 11 illustrates these data.

  With respect to the set of trial data shown in FIG. 11, experiments were performed on the TBAP proposed in this example and a normal AP. The main purpose is to confirm the range of the parameter λ for convergence and the effect of the time window parameter ω. Through repeated experiments, the selection of the parameter λε [0.3,1.0−ε] depends on the characteristics of the data. However, ε is a small positive amount, and ε = 0.02 in the experiment of FIG.

Table 1 shows the tendency of convergence and the calculation time. Convergence was checked by the L ₁ norm of a (i, k) and r (i, k) normalized by the initial value to see if it was less than 10 ⁻⁵ . Table 1 shows the number of typical still images “exemplars”, the number of iterations “iterations”, and the number of message passing “message passing” when the parameter ω of the time window W is changed. From Table 1, it can be seen that, for example, when ω = 10, the TBAP of this embodiment is 6 times faster than the message transmission of a normal AP.

  When ω = 1, it means that all frames are typical still images. ω = n = 100 corresponds to the case of a normal AP that does not include time-dependent typical still image extraction. This was obtained as a comparative example in order to see the convergence tendency. In the case of ω = 5, 10, 20, 50, a monotonic increase is observed in the number of message transmissions, which is directly related to the CPU time because of the size of the time window. However, since the ratio of the number of message transmissions of TBAP to the number of message transmissions of normal AP is kept small, it can be said that these are in a desirable range.

  TBAP was applied to find a typical still image with a reliable frame for the prepared moving image set of FIG. 10 (classes 1 to 20). This is an important procedure for assigning “numerical annotations” to each moving image. The unorganized set of moving images shown in FIG. 10 is structured in terms of numerical tags. Is equivalent. Such tags can be calculated either online or offline.

Thus, the distance obtained from the Similarity measure s (i, j) for each of the typical still images of the two classes of moving images (moving image v _A and moving image v _B ) obtained by TBAP. An example of the matrix is shown in FIG. In the figure, since the moving image v _A has four typical still images and the moving image v _B has three typical still images, the matrix is a 3 × 4 matrix. The numbers in the table represent the components of the distance matrix between the typical still images (representative frames) of the moving image v _A and the moving image v _B. For example, the representative frame 2 of the moving image v _A and the moving image v _B The distance from the representative frame 3 is 0.26. The distance is quantified corresponding to the degree of similarity between the representative frames. Here, the smaller the distance, the more similar the representative frames, and the larger the distance, the more different the representative frames are from each other. Become.

FIG. 13 is an example of a table created by applying the above-mentioned M distance for global alignment. In creating this global alignment table, the algorithm parameters were set to bar (D) = 1 / √ (1− (1 / d)), d = 3 × 256 = 768, g = 0.05, respectively. . In the figure, numeral 26.60 described at the lower right of the table is the numerical value f _last of the final component, and the optimal path traced from there is shown by shading as global alignment. Thereafter, in order to obtain the similarity u (A, B) between the moving image v _A and the moving image v _B , the calculated numerical value f _last is normalized by an averaging function. For example, when normalization is performed using the sum of products of the gap g and the set of the number of frames, the sum is 0.05 × (8 + 12 + 10 + 7) + 0.05 × (12 + 7 + 10) = 1.85 + 1.45 = 3.30 in FIG. The normalized similarity u (A, B) is calculated as 26.60 / (1.85 + 1.45) = 0.06. The matching pattern can be found by tracing the arrow from the last row and last column of the matrix. In this way, it is possible to calculate an appropriate similarity u (A, B) between the moving image v _A and the moving image v _B based on the weighted M distance for global alignment.

FIG. 14 is an example of a table created by applying the M distance for local alignment described above. The algorithm parameters were set as bar (D) = √ (1− (1 / d)), d = 3 × 256 = 768, g = 0.05. In the local alignment table, it can be confirmed that the components whose scores are negative in the global alignment table, that is, the components calculated in Equations 16 and 17, are all reset to zero. Here, the maximum value f _max is 26.95, and the optimum path traced from the component of the maximum value f _max is indicated by shading as local alignment. Thus, even if the moving images to be compared are greatly different, the appropriate similarity u (A, B) is calculated between the moving image v _A and the moving image v _B by the weighted M distance for local alignment. Is possible.

  As a preferred modification, the above-described calculation of the similarity based on the M distance uses only an arbitrary width r for the ratio of the entire sequence as shown in FIG. 15 in order to reduce the amount of calculation. You can also. This is a calculation method that is speeded up by specializing the M distance in similarity calculation of content-based moving image search. In FIG. 15, a blacked portion indicates a place where calculation is omitted. This figure also corresponds to the table of FIG. 13 with global alignment. In this case, the range of calculation is determined by the following equation (22).

In Equation 22, m is the number of representative frames of the moving image v _A , and n is the number of representative frames of the moving image v _B. The width r is a parameter representing the degree of narrowing of the calculation range in the similarity comparison, and is 100 × (1 compared to the calculation for calculating all matrix components by narrowing the calculation range as shown in Equation 22. -R) The calculation amount can be reduced by ² %. In the example of FIG. 15, it can be confirmed that although the calculation range is narrowed, the same result as the calculation result of FIG. 13 in which the calculation range is not narrowed is calculated.

  Next, the relationship between the above-described time window parameter ω and the recall and relevance ratio after calculating the similarity u (A, B) will be described. Here, after all the moving images are classified in descending order of similarity, the recall rate and the matching rate are defined as in the following Expression 23.

Recall rate: = Number of correct moving images found by search / Number of moving images belonging to the same class Precision: = Number of correct moving images found by searching / Number of upper moving images searched

  The reproduction rate means the ratio of search results that satisfy the search request to all moving images that satisfy the search request, and is an index that represents the completeness of the search. On the other hand, the relevance rate represents the ratio of search results that satisfy the search request to all search results, and is an index that represents the accuracy of the search. Generally, the higher the recall and relevance rate, the higher the search performance.

  FIG. 16 shows the result of the precision-recall rate curve obtained in the experiment. In the figure, the vertical axis represents the precision, and the horizontal axis represents the recall. The higher the curve goes to the upper right of the graph, the higher the search performance. Here, each experiment in which time window parameters to which TBAP is applied is “ω = 5” and “ω = 10” is shown. As described in the frame in the figure, the function h (x) expressed by Equation 20 was defined, and the coefficient a used therein was set to 1. For comparison, the experimental results of “Plain AP” using ordinary AP are also shown.

  From these experimental results, in the region of interest that requires a recall rate of up to 20% (the region surrounded by “ROI” in the figure), the precision of TBAP in this example is very high and the processing capability is satisfactory. It can be read that. On the other hand, since the normal AP does not consider the time axis, it can be seen that the performance is inferior to the TBAP of the present invention.

  As mentioned above, the system configuration and algorithm of the moving image search apparatus in the present embodiment have been presented. The moving image has a large capacity size, and each typical still image and a set of frames for which they are responsible are usually calculated offline. . Therefore, such a set can be used as a numerical label for the structural information of a large data set. In the present embodiment, a new similarity calculation method including the Levenshtein distance is proposed as the M distance in consideration that each typical still image includes a responsible frame. This M distance can be used for both the global alignment and the local alignment for the selected typical still image.

In particular, in this embodiment, the idea of performing a moving image search by giving a soft label that gives a mutual relationship to a large amount of moving images and comparing them is shown, and the features thereof are as follows.
-Select multiple frames in each video as typical still images.
Each typical still image includes a responsible frame and has a number of nearby frames that are in the power range.
-It is possible to obtain a calculation method that can compare similarities between typical still image sets of different numbers of sheets and different power ranges as numerical values, and also enables high speed. This is a search between moving images. This search is a complete generalization of the method for measuring the similarity of life information sequences, and can also lead to new developments in this direction.
・ As a method to automatically calculate the typical still image and its power range in a given moving image, the time progression characteristic of the moving image can be reflected by introducing a time window into the normal affinity propagation method. It has become. This is a search within a single video (intra-video retrieval) and can be calculated off-line.

  In this embodiment, feature amounts (for example, luminance histograms) are extracted from each frame of a moving image, and clustered using, for example, an AP to obtain a representative frame for each scene. At this time, by limiting the number of frames to which the AP is applied using a time window of a predetermined time width, a time-series representative frame sequence that allows a gap (gap) between the query moving image and the search target moving image is obtained. A search is performed by extracting and determining the similarity between representative frames and the similarity in time series. In this determination method, a new M distance with a gap penalty g introduced was proposed, and the desired recall and relevance rate could be achieved.

  As described above, the present embodiment uses a system of a moving image search apparatus that calculates the similarity of a target moving image to be searched with respect to a query moving image and searches for moving images similar to the query moving image. We propose a video search method. In particular, this method consists of the following three steps.

  That is, in the first step, the first feature quantity extraction unit 12 or the second feature quantity extraction unit 22 as the feature quantity extraction unit incorporated in the processing device 2 is obtained from each frame of the query moving image and the target moving image. Preferably, each feature amount is extracted using CSD. In the second step, the query moving image representative frame selecting unit 13 and the target moving image representative frame selecting unit 23 as the representative frame selecting unit incorporated in the processing device 2 preferably perform TBAP or target moving image on the query moving image and the target moving image. In the time range limited by the time window using the improved k-means method and the improved harmonic competition method, each frame is clustered from the relationship between the feature values obtained in the first step. Slide on the time axis. Thereby, a representative frame is acquired in time series for each scene. Further, in the third step, the similarity calculation unit 31 or the similar moving image display control unit 32 as the moving image search unit incorporated in the processing device 2 performs the process of representing the representative frame in the query moving image and the representative frame in the target moving image. The similarity between the query moving image and the target moving image is obtained from the similarity between the representative frames, and a moving image similar to the query moving image is searched.

  When such a method is adopted, the feature amount of each frame is calculated for frames within the time width limited by the time window while sliding the time window on the time axis with respect to the query moving image and the target moving image. Based clustering can be performed with less computational cost. Therefore, it is possible to acquire a representative frame for each scene in consideration of time series, particularly for a moving image having a time axis. Then, by using this time-series representative frame and determining similarity between the query moving image and the target moving image, a moving image similar to the query moving image can be retrieved from the target moving images. In this way, by providing a means for calculating the interrelationship, that is, the phase of a large number of moving images numerically, search and grouping using the moving images themselves as queries can be easily performed with high accuracy while keeping the calculation cost low. It becomes possible.

In the third step, the frame number E ^A _i represented by the i-th representative frame of the query image and the frame number E ^B _j represented by the j-th representative frame of the target moving image are obtained. A similarity measure s (i, j) between the i-th representative frame of the query image obtained by TBAP and the j-th representative frame of the target moving image is acquired as the similarity between the representative frames.

Then, after setting the gap penalty g, when the number of representative frames in the query moving image is m and the number of representative frames in the target moving image is n, each (m + 1) × (n + 1) matrix For the component f (i, j), each component f (0, j) in the row where i = 0 is calculated based on the equation 16, and each component f (i, 0) in the column where j = 0 is calculated as the equation 17 Calculate based on Further, when the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i) other than the row of i = 0 and the column of j = 0. , J) is calculated based on equation (18). When the numerical value f _last of the last row and the last column of the matrix is calculated in this way, the similarity u (A, B) between the query moving image and the target moving image is calculated by using the numerical value f _last , for example, using Equation 20. Search for a video that is similar to the query video

  If such a method is adopted, even if the number of representative frames is different between the query moving image and the target moving image, the similarity between both the representative frames and its time series can be obtained by introducing the gap penalty g. It is possible to perform a search by correctly determining the similarity of. Also, a global alignment path can be obtained from each component of the matrix f (i, j) thus obtained. In addition, the calculation of similarity suitable for the moving image data obtained here includes the Levenshtein distance and the Needleman-Wunsch algorithm as mere special cases, and can be applied to a technique for measuring the similarity of life information sequences. .

As another method, in the third step, the number of frames E ^A _i , E ^B _j and Similarity measure s (i, j) are acquired, and after setting the gap penalty g, (m + 1) × ( For each component f (i, j) of the matrix of (n + 1), all the components f (0, j) in the row where i = 0 and each component f (i, 0) in the column where j = 0 are all set to 0. Set. Then, assuming that the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i) other than the row of i = 0 and the column of j = 0. , J) is calculated based on Equation 21. When the maximum value f _max is calculated in each element of the matrix in this way, the similarity u (A, B) between the query moving image and the target moving image is calculated by using the numerical value f _max , for example, in Expression 20. f _last is calculated in place of f _max , and a moving image similar to the query moving image is searched.

  Even in this case, even if the number of representative frames is different between the query moving image and the target moving image, by introducing the gap penalty g, the similarity between both the representative frames and the similarity in time series thereof can be obtained. A search can be performed with correct judgment. Further, a path of local alignment can be obtained from each component of the matrix f (i, j) thus obtained. In addition, the calculation of the similarity suitable for the moving image data obtained here includes the Smith-Waterman algorithm as a special case, and can be applied to a technique for measuring the similarity of life information sequences.

  In the moving image search method described above, it is preferable to acquire a representative frame by TBAP, particularly in the second step. In other words, TBAP makes it possible to select a representative frame in one step from a series of image frames in a time window as a calculation target, thereby simplifying the calculation procedure.

  The above-described effects are obtained by a moving image search apparatus capable of executing the first to third steps, and a moving image search program capable of causing the processing apparatus 2 that is a computer to function the moving image search apparatus. This is also realized in the same way.

  The embodiments of the present invention have been described using the embodiments. However, the present invention is not limited to these embodiments, and can be implemented in various forms without departing from the gist of the present invention. Of course you get. For example, the setting of each parameter value described above can be changed as appropriate by operating the input means 4.

  The present invention can be used in the information processing method and the information processing apparatus manufacturing industry described above. Note that the concept of similarity presented in the present invention is a complete generalization of a method for measuring the similarity of life information sequences, and can be applied in this direction. In particular, the TBAP according to the present invention can be widely applied to data having time series information. For example, in the field of natural language processing, it can be used for topic extraction considering time series. In this way, TBAP is expected to be used in various fields in the future.

12 First feature quantity extraction means (feature quantity extraction means)
13 Query moving picture representative frame selection means (representative frame selection means)
22 Second feature quantity extraction means (feature quantity extraction means)
23 Target moving image representative frame selection means (representative frame selection means)
31 Similarity calculation means (moving image search means)
32 Similar moving image display control means (moving image search means)

Claims (9)

A moving image search method by a moving image search apparatus for calculating a similarity of a target moving image with respect to a query moving image and searching for a moving image similar to the query moving image,
A first step of extracting a feature amount from each frame of the query moving image and the target moving image;
For the query moving image and the target moving image, the frames are clustered from the relationship between the feature amounts within a time width limited by the time window, and the time window is slid on the time axis. A second step of acquiring a representative frame in time series for each scene;
From the representative frame similarity between the representative frame in the query video and the representative frame in the target video, the similarity between the query video and the target video is obtained, And a third step of searching for the moving image similar to the query moving image. In the third step,
The number of frames E ^A _i represented by the i th representative frame of the query image, the number of frames E ^B _j represented by the j th representative frame of the target moving image, and the i th representative frame of the query image Obtaining the inter-representative frame similarity s (i, j) with the j-th representative frame of the target moving image,
Set gap penalty g,
When the number of the representative frames in the query moving image is m and the number of the representative frames in the target moving image is n, each component f (i, j) of the matrix of (m + 1) × (n + 1) about,
Calculate each component f (0, j) of the row of i = 0 based on the following equation 1;
Calculate each component f (i, 0) in the column of j = 0 based on the following formula 2;
When the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i, j) other than i = 0 rows and j = 0 columns are used. j) is calculated based on the following equation 3,
The moving image search method according to claim 1, wherein the similarity between the query moving image and the target moving image is calculated using a numerical value of a last row and a last column of the matrix. In the third step,
The number of frames E ^A _i represented by the i th representative frame of the query image, the number of frames E ^B _j represented by the j th representative frame of the target moving image, and the i th representative frame of the query image Obtaining the inter-representative frame similarity s (i, j) with the j-th representative frame of the target moving image,
Set gap penalty g,
When the number of the representative frames in the query moving image is m and the number of the representative frames in the target moving image is n, each component f (i, j) of the matrix of (m + 1) × (n + 1) about,
Each component f (0, j) in the row with i = 0 and each component f (i, 0) in the column with j = 0 are all set to 0,
When the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i, j) other than i = 0 rows and j = 0 columns are used. j) is calculated based on the following equation 4,
The moving image search method according to claim 1, wherein the similarity between the query moving image and the target moving image is calculated using a maximum value among the components of the matrix.   The moving image search method according to claim 1, wherein in the second step, the representative frame is acquired by a time-constrained affinity propagation method. A moving image search apparatus for calculating a similarity of a target moving image to be searched with respect to a query moving image and searching for a moving image similar to the query moving image,
Feature amount extraction means for extracting a feature amount from each frame of the query moving image and the target moving image;
For the query moving image and the target moving image, the frames are clustered from the relationship between the feature amounts within a time width limited by the time window, and the time window is slid on the time axis. Representative frame selection means for acquiring representative frames in time series for each scene;
From the representative frame similarity between the representative frame in the query video and the representative frame in the target video, the similarity between the query video and the target video is obtained, A moving image search device comprising: moving image search means for searching for a moving image similar to a query moving image. The moving image search means includes
The number of frames E ^A _i represented by the i th representative frame of the query image, the number of frames E ^B _j represented by the j th representative frame of the target moving image, and the i th representative frame of the query image Obtaining the inter-representative frame similarity s (i, j) with the j-th representative frame of the target moving image,
Set gap penalty g,
When the number of the representative frames in the query moving image is m and the number of the representative frames in the target moving image is n, each component f (i, j) of the matrix of (m + 1) × (n + 1) about,
Calculate each component f (0, j) in the row of i = 0 based on the following equation 5:
Calculate each component f (i, 0) in the column of j = 0 based on the following equation 6:
When the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i, j) other than i = 0 rows and j = 0 columns are used. j) is calculated based on the following equation 7,
6. The moving image search apparatus according to claim 5, wherein the similarity between the query moving image and the target moving image is calculated using a numerical value of a last row and a last column of the matrix. . The moving image search means includes
The number of frames E ^A _i represented by the i th representative frame of the query image, the number of frames E ^B _j represented by the j th representative frame of the target moving image, and the i th representative frame of the query image Obtaining the inter-representative frame similarity s (i, j) with the j-th representative frame of the target moving image,
Set gap penalty g,
When the number of the representative frames in the query moving image is m and the number of the representative frames in the target moving image is n, each component f (i, j) of the matrix of (m + 1) × (n + 1) about,
Each component f (0, j) in the row with i = 0 and each component f (i, 0) in the column with j = 0 are all set to 0,
When the weight calculated according to the number of frames E ^A _i and E ^B _j is r (i, j), the remaining matrix components f (i, j) other than i = 0 rows and j = 0 columns are used. j) is calculated based on the following equation 8,
6. The moving image search according to claim 5, wherein the similarity between the query moving image and the target moving image is calculated using a maximum value among the components of the matrix. apparatus.   The moving image search apparatus according to claim 5, wherein the representative frame selection unit is configured to acquire the representative frame by a time-constrained affinity propagation method. A moving picture search program for causing a computer to function as the moving picture search apparatus according to any one of claims 5 to 8.