JP5685324B2 - Method and apparatus for comparing pictures - Google Patents

Description

  The present invention relates to a method and apparatus for comparing images.

  For example, YouTube (registered trademark), Google Video, and Yahoo! In video sharing websites such as Video, video content can be uploaded to the site by the user and made available to others by a search engine. Current web video search engines are believed to provide a list of search results ranked according to their associated score based on specific text queries entered by the user. The user must then review the results to find one or more videos of interest.

  It's easy for users to upload videos to the host, get the videos, make some corrections and distribute them again, so the video search results will have potentially very many or nearly duplicate content Exists. Such replicas would be considered “essentially the same” by the user based on their overall content and subjective impressions. For example, the duplicate video content may include video sequences that are the same or nearly the same content but in different file formats, have different encoding parameters, and / or have different lengths. Other differences include photometric variations, such as color and / or lighting changes, and / or minor editing operations in the space and time domains, such as adding or modifying captions, logos, and / or borders There is. These examples are not intended to be exhaustive lists, and other types of differences may occur in the duplicate video.

  The proliferation of duplicate images can make it difficult or inconvenient for users to find the content they actually want. For example, youtube, google video, Yahoo! Based on a sample query from Video, we can see that on average, there are nearly 27% of the videos listed in the search results, with the most popular being the most duplicated in the results. It is. Given a high proportion of duplicate video in the search results, the user must spend a considerable amount of time separating the search results to find the video that the user needs, and make a similar copy of the video already seen. You have to watch it repeatedly. The duplicate results reduce the value of the video search, retrieval, and browsing user experience. Furthermore, such replicated video content increases network overhead by storing and transmitting the replicated video data across the network.

  One type of video copy detection technique is sequence matching. In sequence matching, a certain time interval having a plurality of frames is a reference for comparing the similarity between the query video and the target video. This typically extracts a sequence of characteristics from both the query video frame and the target video frame, which can be based on, for example, order, motion, color, and centroid. The extracted feature sequences are then compared to determine the similarity distance between the videos. For example, when the order identification characteristic is used, each video frame is first divided into N1 × N2 blocks, and the average brightness of each block is calculated. For each frame, the blocks are then ranked according to their average brightness. The ranking order is considered as an order measure for that frame. The sequence of the order scale for one video is compared with that of the other to evaluate the similarity between them.

  Sequence matching makes it possible to determine the beginning of the overlap position between duplicate images. The sequence matching approach is suitable for identifying almost identical videos, as well as copies of videos with format changes such as coding and frame resolution changes, and those with minor edits in the spatial and temporal domains. Specifically, by using spatial and temporal order identification characteristics, video digitization / coding processes (eg, color, brightness, and histogram equalization, changes in coding parameters), and display format conversion (eg, Detection of video distortion introduced by conversion to letterbox or pillarbox) and partial content changes (eg cropping and zooming in).

  The sequence matching technique is relatively easy to compute and results in a compact display of the frame, especially when using an ordinal measure. Sequence matching tends to be computationally efficient, and real-time calculations can be performed to process live video. For example, an ordinal measure using a 2 × 2 split of one frame requires only four dimensions to represent each frame and requires fewer comparison points between the two frames.

  However, existing sequence matching-based techniques cannot detect duplicate video clips that have changes in the frame sequence such as frame insertion, deletion, or replacement. Frame sequence changes are introduced by user editing or by inserting commercials into the video, for example by a video sharing website. Since it is not feasible to pre-estimate the type of user modification, the inability to detect frame sequence changes limits the applicability of sequence matching techniques to real problems.

  Existing solutions for detecting duplicate images with frame sequence modifications such as frame insertion, deletion, or replacement are based on key frame matching techniques.

  Key frame matching techniques typically segment the video into a series of key frames to represent the video. Each key frame is then divided into regions and characteristics are extracted from the prominent local regions. The characteristic can be, for example, a color, texture, corner, or shape characteristic for each region. Keyframe matching can detect approximate copies that have undergone a significant degree of editing, such as changes in the temporal order of frames or insertion / deletion. But there are quite a few local characteristics within a keyframe, so keyframes are identified, local characteristics are extracted from each keyframe, and between them to match a video clip with a large amount of video in the database. It is computationally expensive to compare the metric distances.

  Recent work has been directed to improving the speed of keyframe matching methods by fast indexing of feature vectors or by reducing the dimension of feature vectors using statistical information. However, in the case of online analysis, both the cost of segmenting the video into key frames and the cost of extracting local features from the query video are still inevitable. Realizing online real-time video replication detection in a Web 2.0 image sharing environment is a real challenge. The key frame matching technique is more suitable for off-line video redundancy detection using fine-grained analysis to aggregate and classify database videos.

  According to the first aspect of the present invention, a method for comparing a query video and a target video includes dividing a query video frame and a target video frame into a plurality of blocks, and calculating an average brightness value for each block. Steps. A plurality of query time series for the query video is generated, each query time series representing a temporal variation of the average brightness value for blocks from the same location in different frames of the query video. A target time series for the target video is generated, each target time series representing the temporal variation of the average brightness value for blocks from the same location in different frames of the target video. The query time series and the target time series are used to determine whether or not there is an alignment between the query video and the target video. By using the present invention, it is possible to generate a time series that can be compared for similarity. The duplicate images show similarities in their respective time series, which can be used to identify that they are related. The method according to the invention provides efficient video duplication detection by reducing the comparison space between two videos.

  One embodiment includes partitioning the query time series and the target time series into a set of discrete linear sections, respectively, and performing local sequence alignment of the linear sections. Linear segmentation allows the average video brightness to be compressed into a discrete list of linear ascending / descending parts, which can then be compared for alignment.

  In replicated video, overlapping video regions typically do not span the entire length of the video sequence, and similar regions can be separated. Therefore, a local alignment of linear sections is required. In bioinformatics, the Smith-Waterman algorithm is well known for determining similar regions between two nucleotide or protein sequences. The Smith-Waterman algorithm compares all possible length string segments and optimizes the similarity measure. The inventors have recognized that the Smith-Waterman algorithm can be extended to perform local alignment for video brightness classification. Instead of comparing the strings, the lightness linear segments are compared to find a local optimal alignment between the images.

  The Smith-Waterman algorithm is a dynamic programming algorithm for producing optimized searches. This is quite time and memory resource demanding, computational complexity is O (MN), storage capacity is O (min (M, N)), where M and N are sequences to be compared Is the length of

  To accelerate the search process, in one embodiment, instead of aligning all lightness segments, the primary ascending / descending sequence is selected as representing the key distinguishing characteristics of the images being compared. Heuristics provide fast alignment of their major ascents / major declines by removing alignments that are unlikely to result in a successful alignment before doing the more time-consuming Smith-Waterman algorithm Applied for. This reduces the calculation cost. Heuristics facilitate the execution of matching algorithms by removing very different videos and by narrowing down to potentially matching areas for similar videos.

  One embodiment according to the present invention is advantageous when it is not feasible to know the type of user modification in advance before applying the video duplicate detection technique, and allows a sequence matching technique to be used. This further retains the advantages of using sequence matching techniques and provides efficient detection.

  Detection of duplicate video with frame changes using an embodiment according to the present invention can be used by a video sharing website as a user feature, or track royalty payments and detect possible piracy. Can be used by video content providers to detect or reduce network traffic by communication “pipes” (eg Internet service providers (ISPs), peer-to-peer (P2P) system providers, content distribution networks (CDNs)) Can be used to manage storage. This may assist the video sharing website in removing or aggregating the video of nearly duplicates so that the user can provide services for searching, retrieving, and browsing. This also facilitates video content-based searching, for example by detecting similar videos with high quality (HD) or 3D.

  Existing video duplication systems can improve their ability to handle user modifications such as frame insertion, deletion, or replacement by including an embodiment according to the present invention.

  According to a second aspect of the invention, the apparatus is programmed or configured to perform the method according to the first aspect.

  According to a third aspect of the present invention there is provided a data storage medium storing a machine executable program for performing the method according to the first aspect.

  Several embodiments of the present invention will now be described by way of example only with reference to the accompanying drawings.

It is a figure which shows roughly the one step in the image | video which should be compared and a comparison process. Fig. 2 schematically shows a method according to the invention. It is a graph which shows roughly the time change of the lightness with respect to one block. 3 is a graph schematically showing linear segmentation. It is a figure which shows schematically the change of the brightness with respect to the image | video to be compared. FIG. 3 schematically shows a matrix used in the method of FIG. FIG. 3 schematically shows the steps in matching used in the method of FIG. FIG. 3 schematically shows the steps in matching used in the method of FIG. Fig. 1 schematically shows a device according to the invention.

  Referring to FIG. 1, a query video 1 having multiple frames is compared with one or more target videos to determine if they are duplicates.

  Referring to FIG. 2, in 2, each frame in the query video 1 is divided into N1 × N2 blocks. At 3, the average brightness value for each block is calculated. By dividing each frame, the variation of the brightness change in the divided partial area is maintained. At 4, for each block, the calculated average brightness value is plotted against the frame number to generate a query time series. In this embodiment, all blocks are processed to create an N1 × N2 time series associated with video 1. In other embodiments, only selected blocks are needed, and as a result fewer time series than N1 × N2 are generated.

  For comparison, the target video 5 shown in FIG. 1 is based on the query video 1 but has been modified by histogram equalization, luminance addition, and bordering and frame deletion. When the target video 5 is processed in the same manner as described above, the target time series shown in 6 is obtained. It can be seen that the change in brightness for the block from the target video 5 is generally similar in shape to that of video 1. For example, frame number 806 for the query time series at 4 increases the average brightness for one block, but decreases that of another block, thereby crossing them. A similar intersection can be seen at frame 739 for the target time series at 6.

  The next step at 7 in FIG. 2 is to capture information resulting from temporal changes in the query and target time series by using a partial linear segmentation technique. By segmenting the time series, the video is compressed and most of the essential information in the temporal change in video brightness is captured. User correction, video distortion, and format conversion are not expected to find an exact match in video replica detection, and the video replica detection process is relatively noisy by ignoring minor changes in brightness over time. It becomes difficult to receive.

  FIG. 3a shows the variation in the average brightness of a portion of one time series, such as that shown in 4 or 6 of FIG. FIG. 3b shows a portion of the time series shown in FIG. 1a after linear segmentation has been applied.

  A bottom-up algorithm is used to segment the time series. The bottom-up method is a well-known approximation algorithm in time series. This starts with the finest possible approximation and iteratively merges the partitions until the termination criteria are met. In this case, linear interpolation is used instead of linear regression to detect the approximate line, because linear interpolation is obtained within a certain time using a low complexity calculation. The quality of fit of potential categories is evaluated using residual errors. The residual error is calculated by taking all the longitudinal differences between the best fit line and the actual data points, squaring them and then summing them.

  In other embodiments, fast linear segmentation of the time series is achieved by an interpolation method using extraction of major maxima and major minima as extreme points. FIG. 4a shows a linear approximation using local maxima and minima. However, the inventors have recognized that depending on these points alone, jump points such as those shown in 8 are excluded. A jump point corresponds to a sudden change in value, for example an upward or downward jump within a short time distance. In the case of a brightness curve of a video block sequence, these jumps usually indicate scene boundaries and are caused by hard cuts or fade-in / out. Thus, in this embodiment, the linear segmentation technique is extended to include jump points, so that the extreme points used in the linear segmentation method are the maximum, minimum, and jump points as shown in FIG. 4b. It becomes.

  After the time series linear segmentation, the main ascending / descending parts in the time series are selected at 9 to provide significant video discrimination characteristics. This can reduce the search space for aligning linear segments.

  Linear segments with longer distances and deeper heights usually represent significant changes in the scene. They are therefore selected as the main climb. Successive major ascending matches show video copies following similar behavior with the same major scene change sequence. In contrast, deep, but very short linear segments are usually associated with scene boundaries such as hard cuts or fades. Such linear sections often contain less information than those that represent changes in the scene. A linear boundary from all the divided blocks is determined to be a scene boundary if it has a deep height within the same short distance that occurs at the same time (ie, the same starting frame ID). These linear segments representing scene boundaries are ignored in the process of selecting the main ascending part.

12, the primary ascending / descending of the query video and the target video to detect an approximate alignment with successive matched ascending / descending parts that are likely to lead to a successful alignment, as shown in FIG. Parts are compared. Referring to FIG. 6, an M1 × M2 matrix is generated, where M1 and M2 are the lengths of the main ascending / descending sequences that are compared. If the two major ascent / descent parts at i and j match, the value “1” is placed in the matrix (i, j). To check the similarity between the linear segment S ₁ [i ₁ ,..., J ₁ ] and the segment S ₂ [i ₂ ,..., J ₂ ], not only the segment height and length, but also the two segments Also consider the similarity of the video frames included in. More precisely, these two categories are similar if:

すなわち２つの区分は同様な長さである。この実装形態では、ｒａｔｉｏ_Ｌ＝０．９である。

That is, the two sections are similar in length. In this implementation, ratio _L = 0.9.

すなわち２つの区分は同様な長さである。この実装形態では、ｒａｔｉｏ_Ｈ＝０．７５である。

That is, the two sections are similar in length. In this implementation, ratio _H = 0.75.

min _p D (p) ≦ dist In other words, the minimum distance between two corresponding frame sequences is at most the threshold constant dist when “sliding” a shorter sequence along a longer sequence, where p Is the range over the starting point of the sliding frame position in the longer image. In this embodiment, due to its efficiency and accuracy, a spatial and temporal order identification characteristic algorithm is selected to calculate the video similarity distance.

Given the two frame sequences F ₁ and F ₂ , the sequence identification characteristic measurement calculates the distance between the following two frame sequences F ₁ and F ₂ :

ただし、Ｌ＝ｊ_１−ｉ_１は、短い方のシーケンスの長さである。

However, L = j ₁ -i ₁ is the length of the shorter sequence.

User correction and video processing techniques can cause differences in video brightness values such as histogram equalization, frame resizing or cropping, brightness / color / hue changes, other added noise, etc. The height of can vary. Similar linear segment distances may also vary due to linear segment approximation errors or other noise introduced by the user. The use of the parameters ratio _H and ratio _L allows some tolerance for these noises. Here, the measured value D (p) based on the order identification characteristic is used to calculate the distance between the two frame sequences, but the matching of the video frame is performed using a matching algorithm based on sequence matching or key frame. It can be based on other global descriptors or even local descriptors used.

  As shown in FIG. 7 after aligning the main ascent, the potential main ascent alignment is expanded to the adjacent non-major ascent to detect further aligned linear segments. This step removes unnecessary alignments in order to reduce the number of comparisons required to apply the Smith-Waterman algorithm in the next stage.

  To detect important approximate alignments in the next step, we use an approach similar to that provided by FASTA, a fast search algorithm used to detect similar DNA and protein sequences. Recognized that it can be executed. As shown in FIG. 8 (a), all diagonal lines of consecutive values “1” in the matrix are identified. Next, as shown in FIG. 8 (b), diagonals whose length is longer than a predefined threshold are retained and single matches and short aligned segments are ignored. Next, as shown in FIG. 8C, the top K longest diagonal lines are selected. In order to extend the overall length of the alignment, an attempt is made to join those sections of the top K diagonals close to each other to form longer sections. Within the combined longer section, gaps are allowed to allow for frame insertion, deletion, and replacement.

  When adjacent diagonals are connected, points with matching diagonals are assigned a scoring score, and gaps or mismatches are given a deduction score. A score is obtained by adding the score added to each of the connected diagonals and subtracting the gap deduction. As shown in Figure 8 (d), if the concatenated approximate alignment score exceeds a given threshold, then join the previously ignored initial short aligned segment around the concatenated segment A check is then made to determine if an approximate alignment with a gap can be formed. Finally, a local approximate alignment with a final score that exceeds the threshold is selected for further review.

  The next step at 15 is a fine-grained alignment of all lightness linear segments of the compared video by applying the Smith-Waterman algorithm. A list of linear lightness segments that can lead to a successful alignment can be determined based on the previously detected approximate alignment of the major ascending / descending parts. The Smith-Waterman algorithm need only look at a limited range of linear segments.

The Smith-Waterman algorithm uses edit distances to detect optimal alignment. This builds a scoring matrix H as follows:
H (i, 0) = 0, 0 ≦ i ≦ M
H (0, j) = 0, 0 ≦ j ≦ N

０≦ｉ≦Ｍ、０≦ｊ≦Ｎ
ただしｘおよびｙは、アラインメントする可能性のある線形区分のリスト、ＭおよびＮはｘおよびｙシーケンスの長さ、ω（ｘ_ｉ，ｙ_ｊ）はスコア付けスキームである。ｘ_ｉとｙ_ｊがマッチする場合はω（ｘ_ｉ，ｙ_ｊ）は正であり、それらがマッチしない場合は負である。挿入および削除に対しては、ω（ｘ_ｉ，−）およびω（−，ｙ_ｊ）は負である。

0 ≦ i ≦ M, 0 ≦ j ≦ N
Where x and y are lists of linear segments that may be aligned, M and N are the lengths of the x and y sequences, and ω (x _i , y _j ) is the scoring scheme. When x _i and y _j match, ω (x _i , y _j ) is positive, and when they do not match, it is negative. For insertions and deletions, ω (x _i , −) and ω (−, y _j ) are negative.

  The Smith-Waterman algorithm detects local alignments by searching for local maxima in the matrix H and then follows the optimal path depending on the direction of motion used to construct the matrix. This keeps this process until a score of 0 is reached. At 16 after the local optimal alignment is obtained, the video similarity distance is calculated by applying existing sequence matching techniques to find a matching linear segment. In this embodiment, an order scale having a 2 × 2 split is used to determine the video similarity distance. If it is found at 17 that the distance is less than the threshold, the two compared images are considered to be duplicates.

  Next, at 18, the alignment at the video frame level is examined for the linear segment instead of the linear segment level. Since the optimal local alignment is based on a lightness linear partition, if a frame change occurs within a partition, the entire partition is considered not a match using the Smith-Waterman algorithm as described above. In order to detect potential matching positions within the unmatched section, a frame-to-frame comparison is performed to calculate a frame-level similarity distance. If the frame similarity distance is less than the video similarity distance obtained using the Smith-Waterman algorithm, the frames are considered to match. This ensures that the similarity distance of matching frames in those unmatched segments does not exceed the average video similarity distance obtained from the remaining matched segments. The frame comparison starts at both the beginning and end of the unmatched section toward the middle of the section. Matching is continued until the frame similarity distance is greater than the video similarity distance. Next, the video overlap position is updated.

  Therefore, in this embodiment, the brightness values of the divided blocks are initially considered as time series. The time series is then partitioned into a list of discrete linear representations. A local sequence alignment of these linear segments is performed to find the optimal matching position. A video similarity distance is then calculated based on the potential alignment position. If the best matching similarity distance is less than a given threshold, the two videos are considered duplicates. To handle frame changes, the existence of gaps, frame insertions, deletions, and substitutions is allowed when comparing linear sequence partitions.

  Referring to FIG. 9, the video management apparatus includes a database or storage device 19 that holds video files. Database 19 may be accessible to the user through the Internet, or may be, for example, a library or other storage location with limited access. Other types of storage devices or databases can be used in place of or in addition to these possibilities.

  The user submits the video Q through the user interface 20 to transmit the video Q that the user wants to add to the database 19. The video Q is sent to the video database 19 and also to the divider 21. In stage 1 of operation, the divider 21 divides each frame of the video Q into N1 × N2 blocks. Calculator 22 calculates an average brightness value for each of the blocks.

  In stage 2, average brightness value data is received from the calculator 22 by the segmenter 23. The segmenter 23 segments the change in average brightness of each block. The sorter 24 then sorts the linear segments from all blocks based on the segment start frame ID into a sorted list. The selector 25 receives the sorted list and selects a major ascending / major descending from the sorted list.

  In the next stage, stage 3, aligner 26 performs an approximate match between the selected primary ascending and descending parts of the query video and those of one or more target videos that have undergone similar processing. Try to detect. The result is tested by the first comparator 27. If there is no similarity as determined for a given threshold parameter, the query video and one or more target videos are considered not duplicates and the duplicate detection process ends at 28.

  If the comparator 27 detects an approximate alignment, the Smith-Waterman algorithm banded in step 4 is applied by the processor 29 and the result is applied to a similar similarity distance calculator 30. The output of the similarity distance calculator 30 is checked against a given threshold by the second comparator 31. If the similarity is insufficient, the compared video is considered not a replica and the process ends at 32.

  If there is sufficient similarity, at step 5, the frame matcher 33 checks the position of the unmatched frame for video insertion, deletion or replacement.

  The result of the duplicate detection process is sent to the video database 19 for use in managing the stored video. If the query video is found not to be a replica, the video database 19 accepts it for storage. If the query video is found to be a duplicate, in one embodiment, the video database 19 then rejects the query video with or without a message to inform the user.

  In an alternative embodiment or alternative, if the query video is found to be a duplicate, it is accepted into the video database 19, but preferably it has a reference to the matched target video and is displayed as a replica. Is done. Duplicate images can be collected together in a group. When a search performed on the database calls one of the groups, other group elements can be removed from the search results, or any replicas tend to be presented after other non-replicas As such, the search results are given a lower ranking than would otherwise be received.

  The video management apparatus of FIG. 9 can be changed so that the video held in the video database 19 is divided and divided and processed at 21 and 22 before the query video is submitted. For example, in one embodiment, the data obtained when a video is submitted to be examined for a replica can be retained and sent to the video database 19 for storage. If the video is not subsequently accepted by the database 19, the data is deleted. When the video is accepted by the database, the data associated with it is retained and made available for use by the aligner 26. In another embodiment, the video in the video database 19 can be split and processed in stage 1 and stage 2 even though not necessarily used for replica testing. For example, data processing can be performed as part of a preparatory step before opening the database to receive new video.

  The functions of the various elements shown in the figure, including any functional blocks named as “processors”, are dedicated hardware as well as hardware capable of executing software in conjunction with appropriate software. It can be realized by using. When implemented by a processor, these functions can be implemented by a single dedicated processor, a single shared processor, or multiple individual processors that can share a portion thereof. Furthermore, the explicit use of the term “processor” should not be construed to refer exclusively to hardware capable of executing software, but is not limited to digital signal processor (DSP) hardware, network Implicitly includes a processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage it can. Other conventional and / or custom hardware can also be included.

  The present invention may be embodied in other specific forms without departing from its spirit or essential characteristics. The described embodiments are exemplary only in all respects and should not be regarded as limiting. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes that come within the meaning and range of equivalency of the claims are to be embraced within their scope.

Claims (27)

A method for comparing a query video with a target video in a video management device ,
By the video management device,
Dividing the query video frame and the target video frame into a plurality of blocks;
Calculating an average brightness value for each block;
Generating a plurality of query time series for the query video, each query time series representing a temporal variation in average brightness values for blocks from the same location in different frames of the query video; and
Generating a plurality of target time series for the target video, each target time series representing a temporal variation in average brightness values for blocks from the same location in different frames of the target video; and
Determining whether there is an alignment between the query video and the target video using the query time series and the target time series ;
Partitioning the query time series and the target time series into a set of discrete linear sections each;
Performing local sequence alignment of the linear segments . The method of claim 1 , comprising: selecting a major ascending portion and a major descending portion from the segmented time series; and using the major ascending portion and the major descending portion for performing the alignment. The method of claim 2 , wherein the selected major ascending and major descending portions exclude jump ascending and jump descending portions. The main ascender and descender of query image, as compared with the main rise portion and the main descending portion of the target image, comprising the steps of obtaining an approximate alignment with elevated portions and descending portions that match consecutive to claim 1 The method described. 5. The method of claim 4 , comprising matching a primary ascending / primary descending query video sequence with a primary ascending / primary descending target video sequence. The matching step generates a matrix with cells plotting the primary ascending / primary descending query video sequence against the primary ascending / primary descending target video sequence, and if there is a match, an appropriate matrix The method of claim 5 , wherein the method is performed by adding a marker in a cell. 7. The method of claim 6 including the step of extending the primary rise / primary descent to the adjacent non-major rise / non-major fall after aligning the major rise / major fall. 8. The method of claim 7 , comprising identifying a diagonal of successive cells having markers and maintaining a diagonal having a length greater than a given threshold for additional alignment processing. Selecting a K-number of the longest diagonal line, and a step of attempting to combine the divided each other closely spaced included in top K diagonal to form a longer segment, to claim 8 The method described. Give a score that is added to diagonally matching lines and a penalty score for gaps in longer lines, and if the combined score of the connected approximate alignments exceeds a given score threshold, the connected Checking whether previously ignored initial short aligned segments around the defined segments can be combined to form an approximate alignment, and final exceeding the final score threshold for further review and selecting a local approximate alignment with scores method of claim 9. 3. The method of claim 2 , comprising obtaining an approximate alignment of the sections and selecting a set of likely alignments, and then applying a Smith-Waterman algorithm to the selected set. The method of claim 11 , comprising aligning at approximately the frame level to approximately aligned segments that are not included in the selected set.   The method of claim 1, comprising storing the query video in a video database that holds the target video when it is determined that the query video is not a replica of the target video. Dividing the query video frame and the target video frame into a plurality of blocks;
Calculating an average brightness value for each block;
Generating a plurality of query time series for the query video, each query time series representing a temporal variation in average brightness values for blocks from the same location in different frames of the query video; and
Generating a plurality of target time series for the target video, each target time series representing a temporal variation in average brightness values for blocks from the same location in different frames of the target video; and
Determining whether there is an alignment between the query video and the target video using the query time series and the target time series ;
Partitioning the query time series and the target time series into a set of discrete linear sections each;
Performing a local sequence alignment of the linear segments and an apparatus programmed or configured to perform a method. 15. The apparatus of claim 14 , programmed or configured to select a main ascending and a main descending from the segmented time series, and using the main ascending and the main descending for performing the alignment. The apparatus of claim 15 , wherein the selected major rise and fall are excluded jump segments. Programmed or configured to compare the primary ascending and descending parts of the query video with the main ascending and descending parts of the target video to obtain an approximate alignment with consecutive matched ascending and descending parts The apparatus according to claim 14 . 18. The apparatus of claim 17 , programmed or configured to match a primary ascending / primary descending query video sequence with a primary ascending / primary descending target video sequence. Match by generating a matrix with cells that plot the primary ascending / primary descending query video sequence against the primary ascending / primary descending target video sequence, and if there is a match, The apparatus of claim 18 programmed or configured to add a marker in a cell. 20. The apparatus of claim 19 , programmed or configured to extend a primary ascension / primary descent to an adjacent non-major ascension / non-primary descent after aligning a primary ascension / primary descent. . 21. The apparatus of claim 20 , programmed or configured to identify a diagonal of successive cells having markers and to maintain a diagonal having a length greater than a given threshold for additional alignment processing. Claims programmed or configured to select the K longest diagonals and attempt to combine adjacently located segments included in the top K diagonals to form longer segments The apparatus according to 21 . Diagonal matching lines are given scoring scores, gaps in longer lines are given deduction scores, and concatenated approximate alignments combined when the combined score exceeds a given score threshold Check whether the earlier short aligned segments that were previously ignored around the segment can be combined to form an approximate alignment and have a final score that exceeds the final score threshold for further review 23. The apparatus of claim 22 , programmed or configured to select a general approximate alignment. To obtain the approximate alignment of segment select alignments may be successful in one set, and then is programmed or configured to apply the Smith-Waterman algorithm to the selected set of claim 14 apparatus. 25. The apparatus of claim 24 , programmed or configured to perform alignment at a frame level for approximately aligned segments that are not included in a selected set. 15. The apparatus of claim 14 , programmed or configured to store the query video in a video database that holds the target video when it is determined that the query video is not a replica of the target video. Dividing the query video frame and the target video frame into a plurality of blocks;
Calculating an average brightness value for each block;
Generating a plurality of query time series for the query video, each query time series representing a temporal variation in average brightness values for blocks from the same location in different frames of the query video; and
Generating a plurality of target time series for the target video, each target time series representing a temporal variation in average brightness values for blocks from the same location in different frames of the target video; and
Determining whether there is an alignment between the query video and the target video using the query time series and the target time series ;
Partitioning the query time series and the target time series into a set of discrete linear sections each;
A data storage medium storing a machine-executable program for performing a method of managing video content, comprising: performing local sequence alignment of those linear segments .

Images