JP2013070158A - Video retrieval apparatus and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To retrieve a query video and to perform processing at high speed even if the query video includes a video where a part on a time base in a reference video is cut and a telop and a logotype are inserted into the reference video.SOLUTION: A video retrieval apparatus retrieves a query video from a reference video stored in a database 15. The apparatus includes: a video division section 11 for dividing the query video into segments of a prescribed time length and selecting the number of frames, which is previously determined, from the respective segments; a feature amount extracting section 12 for extracting a feature amount showing a feature of the video from the selected frame; a feature amount quantizing section 13 for converting the extracted feature amount into one or more quantization identifiers; and a feature amount accumulating section 14 for storing a video identifier of the selected frame and time information in a list constituting a transposition index corresponding to the quantization identifier.

Description

  The present invention relates to a video search apparatus and a program for inputting a query video and searching for the query video from a reference video stored in a hard disk drive, other media, a network storage, or the like.

  With the recent widespread use of broadband and the increased storage capacity of HDDs (Hard Disk Drives), DVDs (Digital Versatile Disks), Blu-ray discs, etc., digital content has not been approved by the copyright holders or content providers. In addition, sharing and disclosing via a network has become easier, and such illegal sharing and disclosing has become a problem. Technology to automatically detect specific contents that the copyright holder has not permitted free distribution from among a plurality of digital contents by using fingerprints (features) of the digital contents for such problems. Has been proposed.

  In Patent Document 1, the feature amount of content is described using three-dimensional frequency analysis and principal component analysis. This method performs 3D frequency analysis by adding frequency analysis (FFT) in the time axis direction to the coefficient obtained by spatial frequency analysis (DCT), and then the coefficient obtained by 3D frequency analysis by principal component analysis. Feature values are extracted from. In Patent Document 2, the specific content similar to the distributed content is narrowed down using the feature amount used in Patent Document 1, and when it cannot be narrowed down, the most similar to the distributed content using the phase-only correlation method Specific content is determined, and it is determined whether or not the same content is based on a threshold value.

  In Non-Patent Document 1, even when temporal editing is performed such that a part of a video is cut out by extracting a feature amount called a color layout from each frame of the video and sequentially matching a plurality of frames. Detection is possible.

  Further, in Non-Patent Document 2, a feature point called a corner is detected from each frame of an image, a feature amount is extracted from the periphery thereof, and each feature point is matched to perform editing such as clipping. Even if there is, illegally distributed content can be detected.

JP 2005-18675 A JP 2006-285907 A

E. Kasutani and A. Yamada, “The MPEG-7 color layout descriptor: a compact image feature description for high-speed image / video segment retrieval,” in Proc. Of ICIP, 2001, pp. 674-677. J. Law-To et al., “Video Copy Detection: A Comparative Study,” in Proc. ACM CIVR’07, pp. 371-378, 2007.

  However, in the methods disclosed in Patent Documents 1 and 2, since one feature amount is extracted from one moving image content, for example, when editing in the time axis direction such as dividing the moving image content into two is performed. There is a problem that detection is impossible. In the method disclosed in Non-Patent Document 1, since only one feature amount is extracted from the entire screen, there is a problem that detection cannot be performed if spatial editing such as insertion of a telop or logo is performed. Further, in the method disclosed in Non-Patent Document 2, dozens of feature points are extracted from one screen and all of them are matched, so that there is a problem that it takes too much time to extract and match the feature points. is there.

  The present invention has been made in view of such circumstances, even if it is a query video including a video in which a part of the reference video on the time axis is cut out or a telop or logo is inserted in the reference video, It is an object of the present invention to provide a video search apparatus and a program that can search the query video and perform the processing at high speed.

  (1) In order to achieve the above object, the present invention takes the following measures. That is, the video search device of the present invention is a video search device that searches for a query video from a reference video stored in a database, and divides the reference video and the query video into segments of a certain length of time, A video dividing unit that selects a predetermined number of frames from the segment; a feature amount extracting unit that extracts a feature amount indicating a feature of the video from the selected frame; and the extracted feature amount is one or more quantum A feature quantity quantization unit for converting to a segmentation identifier, and a feature quantity for storing the segment video identifier and time information in a list constituting a transposed index based on a set of quantization identifiers corresponding to the segment information of the reference video Based on the accumulation unit and a set of quantization identifiers corresponding to the segment information of the query video, the transposition index. Referring to box, voting by, characterized in that it comprises a transposed index search unit for identifying the video identifier and time information of the reference image including all or part of the query image.

  In this way, the reference video and query video are divided into segments of a certain length of time, a predetermined number of frames are selected from each segment, and feature quantities indicating video features are extracted from the selected frames and extracted. Converting the feature quantity into one or more quantization identifiers, and storing the segment video identifier and time information in a list constituting a transposed index based on a set of quantization identifiers corresponding to the segment information of the reference video, Based on the set of quantization identifiers corresponding to the segment information of the query video, the transposed index is referred to, and the video identifier and time information of the reference video including all or part of the query video are specified by voting. All or a part of the reference video can be cut out on the time axis of the reference video, Be one telop or logo or inserted in the image, it is possible to search query image, and reduce search time, it is possible to refine the search.

  (2) In the video search device of the present invention, the feature amount extraction unit extracts a feature amount for each of one or more predefined regions for each of the selected frames, and the feature amount quantization The unit converts the feature amount extracted for each region into a quantization identifier, and the feature amount storage unit forms a transposed index corresponding to each region based on the quantization identifier for each region. And storing the video identifier and time information of the area.

  As described above, for each of the selected frames, the feature amount is extracted for each of one or more predefined regions, and the feature amount quantization unit calculates the feature amount extracted for each region as a quantization identifier. Since the feature amount accumulation unit stores the video identifier and time information of the region in a list constituting a transposed index corresponding to each region based on the quantization identifier for each region, A plurality of feature amounts can be extracted from the frame, and search accuracy can be improved.

  (3) In the video search device of the present invention, the feature quantity quantization unit has a code book for performing vector quantization, and performs vector quantization on a representative vector that is nearest to the feature quantity. In this way, the feature quantity is converted into a quantized identifier.

  In this way, a code book for vector quantization is provided, and the feature quantity is converted into a quantization identifier by performing vector quantization on the representative vector that is closest to the feature quantity, and the quantization identifier Since the matching is performed based on the above, the search time can be shortened.

  (4) In the video search device according to the present invention, the feature quantization unit quantizes the feature value by performing vector quantization on k (k is a natural number) representative vectors in order from the nearest neighbor. It is characterized by converting it into a digitized identifier.

  In this manner, by performing vector quantization on k (k is a natural number) representative vectors in order from the nearest neighbor, the probability that similar feature amounts share the same quantization identifier is improved. The accuracy can be increased.

  (5) In the video search device of the present invention, the feature quantity quantization unit quantizes the feature quantity by discretizing a value of an inner product between the feature quantity and a predefined base with a prescribed threshold. It is characterized by being converted to an identifier.

  In this way, by discretizing the inner product value of the feature quantity and the predefined base with a prescribed threshold, the feature quantity is converted into a quantized identifier, and matching is performed based on the quantized identifier. Time can be shortened.

  (6) In the video search device of the present invention, the feature quantization unit converts the feature into a quantization identifier by discretizing the inner product into one or more values when discretizing the inner product. It is characterized by doing.

  In this way, when discretizing the inner product, by discretizing into one or more values, the probability that similar feature quantities share the same quantization identifier is improved, search time is shortened, It becomes possible to improve the accuracy of the search.

  (7) In the video search device of the present invention, the transposed index search unit refers to a transposed index corresponding to a quantization identifier of each segment of the query video, and the reference video registered in the transposed index is referred to. The video identifier and the video identifier of the reference video that vote for the offset value between the time information of the segment of the reference video and the time information of the segment of the query video, and the number of votes is a certain value or more and within a certain range, and An offset value is used as a detection candidate.

  As described above, the transposed index corresponding to the quantization identifier of each segment of the query video is referred to, the video identifier of the reference video registered in the transposed index, the time information of the segment of the reference video, and the query video Voting is performed for the offset value with the time information of the segment, and the video identifier and offset value of the reference video that has the maximum number of votes within a certain range and the maximum value are used as detection candidates, so that the search time can be shortened. It becomes possible.

  (8) In the video search device of the present invention, for each quantization identifier id assigned to each segment of the query video, the video identifier of the reference video registered in the transposed index is v, and the reference video When the time information of the segment of t is t ′ and the time information of the segment of the query video is t, the transposed index search unit converts the information of (t, id) into the v and the offset value (t '-T) is recorded for each detection candidate, the list of (t, id) is referred to for each of the detection candidates, and the list is divided at a location where t of elements of adjacent lists are separated by a certain distance or more. A score corresponding to each is calculated, and the calculated score is normalized using a value obtained by subtracting the minimum t from the maximum t in the list. And, characterized by a detection result of the normalized value.

  In this way, the information of (t, id) is recorded for each v and offset value (t′−t) at the time of voting, the list of (t, id) is referred to for each detection candidate, The list is divided at locations where t of the element is more than a certain distance, the score corresponding to each divided list is calculated, and the calculated score is normalized using the value obtained by subtracting the minimum t from the maximum t in the list Since the normalized value is used as the detection result, the accuracy of the search can be improved.

  (9) Further, in the video search device of the present invention, the transposed index search unit uses the score of the list of (t, id) as the number of elements in the list.

  (10) Further, in the video search device of the present invention, the transposed index search unit sets the score of the list of (t, id) as a sum of importance levels associated with the id among the elements in the list. The importance is a logarithm of the number of segments accumulated in the inverted index divided by the size of the id-th list of the inverted index.

  Thus, the score of the list of (t, id) is the sum of the importance levels associated with id among the elements in the list, and the importance level is the number of segments accumulated in the transposition index. Since it is the logarithm of what is divided by the size of the id-th list, the importance of quantized identifiers appearing in many segments is reduced, the importance of quantized identifiers unique to a particular segment is increased, and the search The accuracy can be increased.

  (11) In the video search device of the present invention, the transposed index search unit adds a score only once when the same id appears for adjacent t.

  Thus, when calculating the score of the partial list, when the same (r, id) appears for adjacent t, by adding the score only once, particularly in a region with little movement, It is possible to reduce false detections due to the fact that quantized identifiers of unrelated features coincide with each other, and to improve the search accuracy.

  (12) A program according to the present invention is a program for searching a query video from a reference video stored in a database, and divides the reference video and the query video into segments of a predetermined time length, A process of selecting a predetermined number of frames from the above, a process of extracting feature quantities indicating video features from the selected frames, and a process of converting the extracted feature quantities into one or more quantization identifiers And a process of storing the video identifier and time information of the segment in a list constituting a transposed index based on a set of quantization identifiers corresponding to the segment information of the reference video, and the segment information of the query video Based on the set of quantization identifiers, refer to the transposed index, and by voting, A process for specifying an image identifier and time information of the reference image including all or part of the area images, the series of processing, and characterized by causing a computer to execute.

  In this way, the reference video and query video are divided into segments of a certain length of time, a predetermined number of frames are selected from each segment, and feature quantities indicating video features are extracted from the selected frames and extracted. Converting the feature quantity into one or more quantization identifiers, and storing the segment video identifier and time information in a list constituting a transposed index based on a set of quantization identifiers corresponding to the segment information of the reference video, Based on the set of quantization identifiers corresponding to the segment information of the query video, the transposed index is referred to, and the video identifier and time information of the reference video including all or part of the query video are specified by voting. All or a part of the reference video can be cut out on the time axis of the reference video, Be one telop or logo or inserted in the image, it is possible to search query image, and reduce search time, it is possible to refine the search.

  (13) The program of the present invention also includes a process for extracting a feature amount for each of one or more predefined regions for each of the selected frames, and the feature amount extracted for each region is quantized. A process of converting to an identifier, and a process of storing the video identifier and time information of the region in a list constituting a transposed index corresponding to each region based on the quantization identifier for each region. Features.

  As described above, for each of the selected frames, the feature amount is extracted for each of one or more predefined regions, and the feature amount quantization unit calculates the feature amount extracted for each region as a quantization identifier. And the feature amount accumulating unit stores the video identifier and time information of the region in the list constituting the transposed index corresponding to each region based on the quantization identifier for each region. A plurality of feature amounts can be extracted from the frame, and search accuracy can be improved.

  According to the present invention, the query video is divided into segments of a certain length of time, a predetermined number of frames are selected from each segment, and feature quantities indicating video features are extracted from the selected frames, The extracted feature quantity is converted into one or more quantization identifiers, and the video identifier and time information of the selected frame are stored in a list constituting a transposed index corresponding to the quantization identifier. Even if all or part of the reference video is cut out of the time axis of the reference video or a telop or logo is inserted in the reference video, the query video can be searched, reducing the search time and searching. It is possible to improve the accuracy of the.

1 is a block diagram of a video search device according to an embodiment of the present invention. It is a figure which shows a mode that an image | video is divided | segmented. Is a diagram illustrating an example of setting the rectangular region R ^i. Is a diagram illustrating an example of setting the rectangular region R ^i. Is a diagram illustrating an example of setting the rectangular region R ^i. It is a figure which shows the method of extraction of a feature-value. It is a figure which shows an example of soft allocation. It is a figure which shows an example of a transposition index. It is a figure which shows the mode of voting.

  Embodiments of the present invention will be described below with reference to the drawings. In the present embodiment, copyright content to be detected in advance is input as a reference video, the feature amount is extracted, the feature amount is further quantized, and a database is constructed. Thereafter, the reference video is searched using the input query video.

  FIG. 1 is a block diagram of a video search apparatus according to an embodiment of the present invention. As shown in FIG. 1, the video search apparatus 10 includes a video division unit 11, a feature amount extraction unit 12, a feature amount quantization unit 13, a feature amount storage unit 14, a database 15, and a database search unit 16. . These components are connected to the control bus 17 and can transmit / receive signals to / from each other.

The video dividing unit 11 divides the reference video into blocks. FIG. 2 is a diagram showing a state of division. This division includes space division and time direction division. The division in the spatial direction is defined by a rectangle having an arbitrary shape as shown in FIG. The example shown in Figure 2, employs a split shown in Figure 3B, shows a block corresponding to the rectangular R ^4. FIG. 3A shows a case where the entire screen is a single rectangular area. If it is not assumed that captions or logos are inserted, this rectangular area is used. FIG. 3B shows the setting of a rectangular area when the location where editing is performed is not determined in advance. FIG. 3C shows the setting of a rectangular area when editing such as subtitles is assumed at the bottom or right of the screen. Even if editing is performed on either one, the other rectangular area is not affected.

  The division in the time direction is performed by dividing successive frames at a constant time (for example, every 0.5 seconds). A rectangle whose rectangular ID is r and the t-th block in the time direction is expressed as Br, t. If a 30 fps video is divided every 0.5 seconds, there are 15 frames in each block.

  The feature amount extraction unit 12 extracts a feature amount from each block Br, t obtained by the video division unit 11. In this case, feature vectors may be extracted from all the frames included in Br, t. However, if it is desired to limit the number of extracted feature quantities, the feature quantities are extracted after sampling the frames at regular intervals. It may be extracted. For example, a technique using DCT coefficients or a scale-invariant feature transform (SIFT) widely used for describing local feature regions can be used.

  Here, a set of feature amounts extracted from Br, t is Fr, t. Hereinafter, an extraction method when an AC (Alternating Current) component of a DCT coefficient is used as a feature amount will be described. First, the partial frame is reduced to 8 × 8 pixels and discrete cosine transform (DCT) is performed. Of the obtained DCT coefficients, M AC feature components are obtained in the zigzag scan order to obtain M-dimensional feature values.

  The feature quantity quantization unit 13 quantizes the feature quantities in each feature quantity set Fr, t extracted by the feature quantity extraction unit 12 to values from 0 to N−1, respectively, and sets quantization ID sets Wr, t (integer value) is created. The number of IDs in Wr, t is determined in advance by the maximum number or by the number of soft assignments at the time of quantization.

Hereinafter, a method of creating Wr, t when the AC component of the DCT coefficient is used as a feature amount will be described. Each dimension of the M-dimensional feature value is binarized to 1 if it is a positive value and 0 if it is a negative value. As a result, the M-dimensional feature value is converted into an N-bit bit string. There are 2 ^ M kinds of this bit string, and 0-2 ^ M-1 representing this bit string in decimal number is a value after quantization (N = 2 ^ M). By this procedure, Wr, t is obtained. However, soft allocation is performed in order to cope with a change in the quantization ID due to a minute change in the feature amount. The software assignment can be performed using a technique described in the following document, for example.
J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, "Lost in quantization: Improving particular object retrieval in large scale image databases," in Proc. Of CVPR, 2008.

  FIG. 5 is a diagram illustrating an example of software allocation. This soft assignment is not to assign a feature quantity to only one ID at the time of quantization, but to assign it to a plurality of quantization IDs. In the present invention, for each dimension of each feature quantity f of Fr, t, assignment is made to IDs in which the absolute value is small and the bits of the K dimension are freely inverted, thereby assigning a total of 2 ^ K IDs. Done. When the maximum number of IDs is determined, the IDs subjected to bit inversion in order from the smallest absolute value are repeated until the maximum number of IDs is exceeded.

  Note that general feature vectors may be quantized using vector quantization. K-means clustering is performed in advance from a set of feature values to obtain N representative vectors. The feature amounts in Fr and t are assigned to the nearest representative vector, and the ID of the representative vector is set as a quantization ID. Also, soft allocation can be realized by allocating not the nearest representative vector but the nearest K representative vectors.

  In this manner, Wr, t is created. In addition, duplication of quantization ID shall not be permitted.

  The feature amount storage unit 14 stores the set of quantization IDs Wr, t in the transposed index shown in FIG. A transpose index is prepared for each rectangle. As shown in FIG. 6, the information of the block Br, t is registered in the corresponding list for all IDs in Wr, t. The information to be registered is the video ID of the reference video and the time information (t) of the block. This registration is performed for all r and t. The feature amount accumulating unit 14 stores the registration information in the database 15.

  On the other hand, the database search unit 16 searches for the query video from the reference video. When performing a search, the query video is divided into blocks, feature quantities are extracted, and quantization is performed, as in the case of storing the reference video. The block division method must be the same as when the reference video is stored. However, the number of feature quantities extracted when extracting feature quantities is reduced, or the IDs for soft assignment when performing quantization are used. The search speed can be improved by reducing the number.

  For each Wr, t extracted from the query video, the database search unit 16 refers to the corresponding list of transposed indexes for all quantization IDs in Wr, t, and acquires a list of corresponding block IDs. If the block ID in the list is t ', the corresponding offset t'-t is voted. At the same time, information (r, t, id) at the time of voting is stored for each offset value t′−t. Here, id is a quantization identifier. At that time, t is stored so as to be sorted in ascending order.

  FIG. 7 is a diagram illustrating a voting state. When voting is completed for all Wr, t, a list of offset values having a maximum value that is equal to or greater than a threshold is acquired for each offset value score. Thereafter, the following processing is performed for each offset value.

  For the offset value t'-t, a corresponding (r, t, id) list is acquired. As described above, this list is sorted in ascending order with respect to t. This list is divided into partial lists by dividing the list at locations where adjacent t is a certain distance or more. Thereafter, a score is calculated for each partial list. Most simply, the score is the number of elements in the list. Instead of the number of elements, a weight based on id may be used for each element. As this weight, Inverse Document Frequency (IDF) used in document search can be used.

  In the case of the present invention, IDF can be obtained as IDF = log (D ′ / D), where D is the number of stored video segments and D ′ is the size of the id-th inverted index list. Furthermore, the score may be normalized according to the difference between the maximum t and the minimum t in the partial list (= the length of the detected copy area) so that the score decreases as the difference increases. The simplest is to divide the score by the maximum t minus the minimum t.

  Further, when calculating the score of the partial list, if the same (r, id) appears for adjacent t, the score may be added only once.

  After this processing is performed for all offsets, the results are sorted by the partial list score, and the upper result is used as the search result.

  As described above, according to the present embodiment, the query video is divided into segments of a certain length of time, a predetermined number of frames are selected from each segment, and video characteristics are selected from the selected frames. Extracting the feature quantity to be displayed, converting the extracted feature quantity into one or more quantization identifiers, and adding the video identifier and time information of the selected frame to a list constituting a transposed index corresponding to the quantization identifier. Because it is stored, even if all or part of the query video is a part of the reference video cut out on the time axis or a telop or logo is inserted in the reference video, the query video can be searched, It is possible to shorten the search time and increase the accuracy of the search.

DESCRIPTION OF SYMBOLS 10 Image | video search device 11 Image | video division | segmentation part 12 Feature-value extraction part 13 Feature-quantization part 14 Feature-value storage part 15 Database 16 Database search part 17 Control bus

Claims (13)

A video search device for searching a query video from a reference video stored in a database,
A video dividing unit that divides the reference video and the query video into segments of a predetermined time length, and selects a predetermined number of frames from each segment;
A feature amount extraction unit that extracts a feature amount indicating the feature of the video from the selected frame;
A feature quantization unit that converts the extracted feature into one or more quantization identifiers;
Based on a set of quantization identifiers corresponding to the segment information of the reference video, a feature amount storage unit that stores the video identifier and time information of the segment in a list constituting a transposed index;
Based on a set of quantization identifiers corresponding to the segment information of the query video, the transposition index is referenced, and the transposition for specifying the video identifier and time information of the reference video including all or part of the query video by voting An image search device comprising: an index search unit. The feature amount extraction unit extracts a feature amount for each of one or more predefined regions for each of the selected frames,
The feature quantity quantization unit converts the feature quantity extracted for each region into a quantization identifier,
The feature quantity storage unit stores the video identifier and time information of the area in a list constituting a transposed index corresponding to each area based on a quantization identifier for each area. The video search device described.   The feature quantization unit has a code book for vector quantization, and converts the feature into a quantization identifier by performing vector quantization on a representative vector that is closest to the feature The video search apparatus according to claim 1 or 2, wherein   The feature quantity quantization unit converts the feature quantity into a quantization identifier by performing vector quantization on k (k is a natural number) representative vectors in order from the nearest neighbor. The video search device described.   The feature quantity quantization unit converts the feature quantity into a quantization identifier by discretizing a value of an inner product between the feature quantity and a predefined base with a prescribed threshold value. The video search device according to claim 2.   6. The video search according to claim 5, wherein the feature amount quantization unit converts the feature amount into a quantization identifier by discretizing the inner product into one or more values when discretizing the inner product. apparatus.   The transposed index search unit refers to the transposed index corresponding to the quantization identifier of each segment of the query video, the video identifier of the reference video registered in the transposed index, the time information of the segment of the reference video, and the A vote is performed on an offset value with respect to time information of a segment of a query video, and a video identifier and an offset value of a reference video that have a maximum number of votes within a certain range are set as detection candidates. Item 2. The video search device according to Item 1. For each quantization identifier id assigned to each segment of the query video,
The video identifier of the reference video registered in the transposed index is v,
Let t 'be the time information of the reference video segment,
When the time information of the query video segment is t,
The transposed index search unit records the information of (t, id) at the time of voting for each of the v and the offset value (t′−t), and refers to the list of (t, id) for each of the detection candidates. Then, the list is divided at a location where t of the elements of the adjacent lists is more than a certain distance, a score corresponding to each of the divided lists is calculated, and the calculated score is reduced from the maximum t in the list to the minimum 8. The video search apparatus according to claim 7, wherein normalization is performed using a value obtained by subtracting t, and the normalized value is used as a detection result.   9. The video search apparatus according to claim 8, wherein the transposed index search unit uses the score of the list of (t, id) as the number of elements in the list.   The inverted index search unit sets the score of the list of (t, id) as the sum of the importance levels associated with the id among the elements in the list, and the importance levels are accumulated in the inverted index. 9. The video search apparatus according to claim 8, wherein the number of segments is a logarithm of the number obtained by dividing the number of segments by the size of the id-th list of the inverted index.   11. The video search apparatus according to claim 10, wherein the transposed index search unit adds a score only once when the same id appears for adjacent t. A program that searches query video from reference video stored in a database.
Dividing the reference video and the query video into segments of a certain length of time, and selecting a predetermined number of frames from each segment;
Processing for extracting a feature amount indicating a feature of the video from the selected frame;
Converting the extracted feature quantity into one or more quantization identifiers;
Based on a set of quantization identifiers corresponding to the segment information of the reference video, a process of storing the video identifier and time information of the segment in a list constituting a transposed index;
A process of referring to the transposed index based on a set of quantization identifiers corresponding to the segment information of the query video and specifying the video identifier and time information of the reference video including all or part of the query video by voting A program that causes a computer to execute a series of processes. For each selected frame, a process of extracting a feature amount for each of one or more predefined regions;
A process of converting the feature quantity extracted for each region into a quantization identifier;
13. The method according to claim 12, further comprising: storing a video identifier and time information of the region in a list constituting a transposed index corresponding to each region based on the quantization identifier for each region. Program.