System and method for measuring similarity between a set of known temporal media segments and a one or more temporal media streams6675174Abstract This invention is a scaleable system to perform exact matching or similarity matching between a large store of reference temporal media sequences and a query target temporal media sequence. The system is not limited to finding exact matching media segments but also can find media segments that are similar. One kind of similarity between media segments is the similarity between a long commercial and a short commercial, where the short commercial is formed by sub-segments of the longer commercial. Another kind of similarity of two media segment is when they depict three-dimensional actions that are similar and imaged from similar viewpoints. Given a reference media segment, a multitude of features are computed in a consistent way from either predetermined or media content-dependent key intervals. These features are stored in segment index tables along with identifiers of the corresponding reference media segments. At search time, again, a multitude of features is computed from each key interval and now the features are used to search the segment index table for identifiers of stored media segments. If the key intervals are similar, many if not all, features computed from the key intervals point to the same reference media identifier. Claims We claim: Description FIELD OF THE INVENTION
M target media stream in which the reference media streams are to
be recognized
S set of reference media segments to be indexed,
this is the set of known media segments
n number of reference media segments to be indexed
s.sub.i reference media segment i
L.sub.i length of reference media segment i measured in seconds
k.sub.i number of key intervals selected from reference media segment i
k.sub.max largest number of key intervals selected, i.e., max {k.sub.i,
i = 1, . . . , n}
K.sub.i (t) is the key interval t in reference media segment i,
where t = 1 , . . . , k.sub.i
m total number of features used to generate the index codes
F.sub.j the feature j, j = 1, . . . , m.
C.sub.j {c.sub.j1, c.sub.j2, c.sub.j3, . . . , c.sub.jM(j) } the set of
codes for the feature F.sub.j
M(j) cardinality (C.sub.j) is the number of code elements for feature j
W.sub.j number of domain regions (domain codes) for the feature j
(In the case of a windowing of video frames based
on subdivision of the frame in w.sub.1 horizontally and
w.sub.2 vertically, W.sub.j = w.sub.1 .times. w.sub.2)
T segment index table
Part of the feature-based indexing engine of FIG. 2A is t he key interval selection process. This process determines from which sequence of key intervals and/or from which sequence of audio key intervals the features are computed. That is, key interval selection is the process of selecting a subset of the media (visual track, audio track, or other media) for each of the known reference media segments s.sub.i. The key intervals are used in the feature extraction process to generate the features F.sub.j, j=1, . . . , m. This process can be applied to both the audio and visual media of the media segment. The goal of the key-framing process is to generate a representation of the reference media segments in S. These representations must have a lowest possible data rate, while retaining enough data to allow for discrimination between the different samples in the sample set S. There are several variables in the key interval selection process, which will be changed according to the application. The two main variables are the length of the key-interval and the spacing between key intervals. Some applications may choose to select all possible key intervals, where as others may select very widely spaced key intervals. The choice of these parameters will determine the accuracy with which the search process operates. The representations for the different reference media segments s.sub.i are stored in a segment index table described in FIG. 3. Along the x-axis or time (key interval) axis (310), for each key media interval or for each key audio interval, a two-dimensional array holds the feature codes 320 along the negative z-axis 325 and the domain codes 330 along the y-axis 335. Domain codes 340, 342, . . . , 360, . . . , 349 refer to regions in the key interval (media domain) or to regions in the domain of the transformed data in the key interval, for example, to regions in the frequency domain when the Fourier transform is applied to the key intervals. Feature codes 350, 352, . . . , 359 refer to quantization intervals of the feature range. The set of domain codes is denoted by D the set of feature codes is denoted by C. The generation of the feature codes for key intervals is described in FIGS. 4 and 5. Domain codes are described in FIG. 5. In a preferred embodiment, there are two criteria for selecting key intervals (a key interval refers to one or more media frames or an audio interval) from the media, regular sampling and content-based sampling. For regular sampling, the key intervals are chosen at some fixed time offsets within the reference segment s.sub.i. For example, in the case of audio, a key interval could be a 0.5 sec window of the audio signal selected at two second intervals. In the case of video, every 10th frame could be chosen as the key frame (interval) or every 10th through 12th frame could be chosen as a key interval. Of course, irregular samplings like every 1st and every 3rd frame are also possible. In the case of content-based key interval selection, the key intervals are chosen based on properties of the media. For example, in the case of a video signal the key intervals can be chosen based on the location of scene changes. Key intervals can also be picked based on the relative change of content of the video from the beginning of a scene break. For example in the case of video, consider a video shot which provides a view of a scene by panning over different parts of the scene, in this case, key intervals may be selected where the change between different points in the scene is larger than a preset threshold. Further, key intervals can be selected based on motion information in the media, say, where the overall motion is a a local minimum. Or, on the other hand, key intervals can be selected where the motion is constant or at a local maximum. For the audio track, key intervals can be, for example, obtained by taking a window of audio data following a silence or key intervals can be selected based on frequency content. In general, any property of the media content can be used for content-based key interval selection. Each of these criteria has its distinct advantages. Content-based key-framing or interval selection produces a more compact representation of the media. But during the recognition process, the same criteria have to be used on the target media stream and this adds to the amount of computation that needs to be performed at recognition time. The process of regular sampling can be affected by the load on the machine running the recognition process. If the frame rate of the recognition process drops due to the load on the machine, then during reference media segment detection the key-framing or interval selection process may generate spurious key frames or drop valid key frames. This, in turn, would affect the accuracy of the recognition process. Feature code computation consists of feature computation followed by quantization. The feature computation process 405 (see FIG. 4A) has three steps: media region selection 406 followed by media region transformation 407 and region-based feature computation 408. Another possibility for process 405 (FIG. 4B) is media transformation 417 followed by feature region selection 416 and region feature computation 408. The feature code generation process follows feature computation 405 in the form of feature range quantization 415. FIGS. 4A and B show the different steps involved in the process. In the following, in case of FIG. 4A the media is the domain, and in the case of FIG. 4B, the domain of the transformation is the domain. In the former case, the media is a function on the domain, in the latter, the feature is a function on the domain. Compare image function versus Fourier function, i.e., image plane vs. Frequency domain. In other approaches to the problem, the feature extraction and code generation processes are combined into one single step (U.S. Pat. No. 5,504,518 to Ellis et al.). In the present invention, these steps are distinct. The feature transformation and feature extraction steps are dependent on the type of similarity to be measured. For example, image color based coding processes have been discussed in Smith et al. There are several other techniques of media transformation and feature computation that are well known in the art. See Smith and Chang, Tools and Techniques for Color Image Retrieval, In IS&T/SPIE Proc Vol2670, Storage and Retrieval for Image and Video Databases. The feature-based code generation process is applied to all the key intervals selected by the key-framing process. The media target stream M in FIGS. 4A and B is depicted by a horizontal rectangle 450. Time running from time 0 to time T seconds is indicated by the time axis 455. A key frame is selected at time is t.sub.0 (460) or, alternatively, a key interval (470) is selected between times delta.sub.t1 and delta.sub.t2. In general, the feature code computation is comprised of a number of steps. The complexity of each of the steps is dependent on the feature being considered. In this invention, for video we describe in more or less detail two visual features, namely, image color-based codes and optical flow-based codes. We also describe an auditory feature, Fourier transform-based feature code generation. As indicated above, this feature code generation process, that generates feature codes 475, is comprised of two steps, namely, the step where features are extracted 405 and a quantization or code generation step 415. Each of these steps is discussed below. Referring again to FIGS. 4A and B, in the feature extraction step 405, the data in the key intervals are processed to extract different types of measurements or features. These measurements may be based on both global and local spatial or spatio-temporal properties of a key interval. These measurements may also be extracted from predetermined portions (regions) of the key intervals. For example, in FIG. 5 a key frame 510 (media domain) is shown with two arbitrary shaped regions (domain regions) 520 and 530. Only from the data in these regions, the features 475 are computed. The regions here can cover the complete key interval and the regions can differ for each feature F.sub.j with each feature j having a different number of local domain regions W.sub.j. FIG. 6 shows an example where the media domain (key frames) 600 for feature F.sub.j are divided up into 16 rectangular windows (domain regions) 601, 602, . . . , 603, . . . , 604 (the local domain regions). Other windowing schemes are envisioned. FIG. 6A gives an example of a video frame 650 with the window structure 601, 602, . . . , 603, . . . , 604 overlaid. Each window 660 contains data which is used for the domain region transformation 407; the media transformation 405 would use data in the whole frame 650. In the case where the domain regions are windows, with w.sub.1 windows horizontally and w.sub.2 windows vertically we have W.sub.j =w.sub.1.times.w.sub.2 regions. The domain region code (domain code) book (420, FIG. 4A and B) for each feature j which has W.sub.j elements and could be implemented as an array of W.sub.j elements with each element pointing to a local-media region. This array is then stored in the domain code book 420. Another preferred method of implementing these domain codes is depicted in FIG. 5A. Here, as in FIG. 5, two regions 520 and 560 are used in the feature computation process 405 (FIG. 4A). The data points (pixels, samples) in 510 are marked `1` 550 if the points are in region 520 and are marked `2` 560 if the points are in region 530. Data points in 510 that are in neither region are marked `0` 570. In the case of FIG. 5 with two local-media regions 520 and 530 in the media domain (frame) 510, and hence W.sub.j =2, the first element 525 of the domain code book 420 Domain Code(1) 525 refers to region 520 while the second element 535 of the code book 420 Domain Code(2) 535 refers to region 530. Similarly, in FIG. 6 which is used to compute (say) feature F.sub.i with W.sub.i =16, Domain Code(k) 610 refers to local media structuring region k 603. In FIG. 3, the segment index table, the y-axis corresponds to the domain codes in the domain code book 420 referring to the local-media regions, the z-axis corresponds to feature codes which refer to quantized feature values. Referring to FIG. 4A, the code book 420 is used for media region selection 406 every time t.sub.0 (460), i.e., a key interval is encountered. Each feature F.sub.j, j=1, . . . , m is computed from the data in the appropriate regions using the different code books 420 for the different features F.sub.j. The region transformation 407 depicts the transformation of media--into feature space, such features can be color space transformation, edge detection optical flow, etc. In general, the resulting feature values are not directly used as input to the feature quantization step (415). Rather, an intermediate transform 408 is applied that maps the features obtained by region transformation 407 into a smaller number of feature values for each F.sub.j, j=1, . . . , m. An example is to compute the average hue for the regions 601, 602, . . . , 603, . . . , 604 in FIG. 6. Or, it maps a number of high-contrast edge element located in the form of video text into the coordinates of the window that contains the edge elements. In essence, the transformation 408 is a data reduction step so that the representations for the reference media streams S=s.sub.1, . . . , s.sub.n are as small as possible and yet the reference streams can still be distinguished. Referring to FIG. 4B, it is also possible that all the data in the key interval is transformed through a media transform 417 into feature space is G. (In this case, feature space G is the domain.) Hence a mapping 417 is performed of all the data in a key interval into some feature space G. Then local regions of feature space G (feature regions), obtained through feature region selection 416, are used as input to the region feature computation step 408. In this case, the domain code book 420 contains Domain Code(1) . . . Domain Code(W.sub.j) for feature j with each domain code pointing to a local region in space G. An example of this case is the computation of features from the audio track. The key (time) interval now could be [delta.sub.t1, delta.sub.t2 ] (470 in FIG. 4B) and one of the features F can be the Fourier transform of this time interval. This gives the distribution of audio frequencies, from low to high, in the time interval [delta.sub.t1, delta.sub.t2 ]. The domain code book (420) points to regions in the domain [0, f.sub.max) of G of the frequency distribution function (rather than the domain being the key interval). Where f.sub.max is the maximum frequency in the key interval. For instance, the domain code book could point to a subdivision of [0, f.sub.max) into equal sub intervals (regions), and the output of transformation 408 (region-based-feature-computation) could be simply the average value or energy in the sub intervals (this is further explained in FIG. 9). One advantage of using the domain code book, is that the codes generated can be changed by replacing the code book. Further, the codes generated can be dynamically changed based on some property of the key interval, by switching code books. Finally, box 415 in FIGS. 4A and 4B represents the region feature range quantization process, the feature code generation 475. The values of the features extracted from the feature extraction process, which are used for feature code generation, have a bounded range. In order to represent the feature values as part of the segment index table of FIG. 3, the features need to be quantized into a finite set of codes (feature codes 320). The number of feature codes to be generated from a feature and the quantization levels used to generate these codes are critical parameters which depend on the nature of the specific feature and the type of reference segments in the segment set S. For each feature F.sub.j, there exists a set C.sub.j of codes denoted by {C.sub.1, C.sub.2, C.sub.3, C.sub.4, . . . , C.sub.M(j) } with M(j) the cardinality of C.sub.j, the number of code elements for feature j. The feature range code book 430 determines which interval in the range of the feature function F should map into which code. In FIG. 3, the negative z-axis 325 represents the feature codes 320. For each feature F.sub.j that is used in the representation of the reference media streams S a table such as in FIG. 3 is needed. The feature extraction can encompass many different transformations. In the case of visual media, it includes, computing the color histogram of a key frame, computing color histogram of selected spatial regions in the key frame, computing the pixel difference between two or more temporally displaced key frames, computing a measure to detect the presence of high-contrast regions in a key frame (like scene-text) or computing the optical flow or other spatial displacements between two subsequent frames (or possible spaced further apart) within a key interval. FIG. 7 shows this last case. A video stream 710 is the input to a video transformation 720 that computes the optical flow 730 (transformed media). A possible way to implement this is to select key intervals of frames 702 . . . 708 in video stream 710 as input to the video transformation 720. Each key interval is transformed into a feature domain which in this case are individual frames 732 . . . 738 of optical flow. Every pixel in these frame contains two values, x and y, that together represent the optical flow at the pixel in vector form (x, y).sup.t. The optical flow is computed by comparing and matching two or more consecutive frames in the key intervals. Optical flow computation is well known in the prior art. Besides optical flow, any other transformation that has as domain two or more frames, be it consecutive frames or frames spaced apart, and maps this data into a function on some other domain can be used as features for indexing video sequences. In the case of audio, feature extraction could include processes like computing the Fourier transform of a key interval, computing cepstral coefficients of a key interval, etc. In summary, the feature extraction process could be a mapping from key intervals into any finite dimensional space. Below we describe in more detail a key frame representation in terms of hue and an audio key interval in term of frequency magnitude. Recognizing identical segments of video from the set S in a media stream M, can be achieved by using the following frame color codes. The color space of frames (images) has been extensively used for indexing and searching based on image content. Application of hue color code, a preferred embodiment of this invention, is comprised of a number of steps (see FIG. 8A). Color is a good feature for video segment detection or recognition. In particular, the hue component of color contains much information. Hue is the portion of color information that indicates which color a particular pixel in frame 810 has. The colors range from red, green to magenta (see FIG. 8B.) Hence, from the video signal, which is as input to the system is typically in an RGB or YIQ format, the hue component has to be extracted. This requires a transformation from the original color space (RGB or YIQ) of the media to the HSV color space. This is achieved by using the standard algorithms for color space conversions (e.g., Foley & van Dam, Chapter 13). Once the image is transformed in to the HSV model, the hue channel is separated from the HSV model, as the code generation is based on the hue values of the pixels in the key frames. Refer now to the block diagram of FIG. 8A. Let video stream 450 be the input and frame 810 at time t.sub.o 460 be the current key frame. This frame 810 could be in YIQ format and is denoted as YIQ(frame) in FIG. 8A. Then in block 875 the feature (hue) codes 864 for this frame are computed. The domain regions for the frame are rectangular windows, indexed by domain codes D 825, and hence for each domain code d in D, a feature code c from C 855 is determined. The output of step 875 therefore is a list of pairs {(d.sub.i, e.sub.i), i=1, . . . , N}, with N the number domain codes (the number of windows) each e.sub.i, i=1, . . . , N a feature code value from the set of feature codes C. In FIG. 8A, the domain code book 420 contains the the domain codes D, pointing to the media domain (frame) windows, the feature code book 430 contains the feature codes and feature quantization information. That is, how each feature code c is associated with an interval of hue values. The first step in 875 of FIG. 8A, is to convert the the YIQ encoded frame into an HSV encoded frame 815. This is well known in the prior art. The output then of 815 is the hue part of the color information of the frame, denoted as Hue(frame) 820. Domain codes D 825 are pointing to the domain regions which are rectangular as in FIG. 6 with windows 601, 602, . . . , 603, . . . , 604. Block 830 in FIG. 8 divides the frame into windows, as indicated by domain codes D. (Note that the domain subsets need not be rectangular, they can be arbitrarily shaped as show in FIGS. 5 & 5A. Rectangles are a specific case of an arbitrary shaped window.) For example, Domain Code (k) 610 points to the location of window k 603 (see FIG. 6). Further, block 830 outputs Hue(window) 835 for each window 601, 602, . . . , 603, . . . , 604 in the current frame. Subsequently, block 840 determines the average hue, Averagehue(window), in the windows referenced by domain codes D 825. The averaging is the first data reduction step. (Note that other averaging methods are contemplated. For example in one embodiment, the median of the window instead of the average is used and it is more robust to noise.) The second data reduction step in 875, is block 850 which quantizes Average_hue(window) into a hue code e where e is an element of the feature codes 855 C. The mechanics of this quantization is stored in the feature code book 430 and is explained in FIG. 8B. As noted above, the output of step 875 is a list of pairs ((d.sub.i, e.sub.i), i=1, . . . , N), with N the number domain codes and each e.sub.i, i=1, . . . , N a feature code value. There are a number of different ways of extracting feature values Average_hue(window) 845. For example, at one extreme case the hue value at each pixel can be considered as a feature (i.e., the windows are the pixels) or at the other extreme the hue value of all the pixels in the frame can be averaged to generate the feature value (i.e., the window is the frame). In a preferred embodiment, as indicated above, the frame is divided into w.sub.1 windows in one dimension of the image and w.sub.2 windows along the other dimension as in FIG. 6. An average hue value is computed based on the pixels in each window. Thus the hue color for a video key frame is a set of w.sub.1.times.w.sub.2 average hue values. Quantized these give a feature code for each domain code, denoted as ((d, c)), a list of code pairs. In FIG. 8B, 880 is the hue value of a pixel. The hue values can range from 0 degrees to 360 degrees, in FIG. 8B indicated by 860 (0 degrees), 861 (30 degrees), 862 (60 degrees), . . . , 863 (180, degrees), . . . , 864 (330 degrees), 865 (360 degrees). The hue values from 330 degrees (864) through 30 degrees (861) are centered around the color pure red (870), from 30 degrees (861) through 90 degrees around the color pure yellow (871) etc. To arrive at hue (feature) codes 855, the hue value outputs of the averaging operation 840 need to be quantized to populate the segment index table 130. This quantization to generate the hue codes 855 is performed in step 850, using feature code book 430. FIG. 8B gives the hue quantization table 880 that is stored in the feature code book 430. Coding is performed according to the following table There are several different ways in which a feature can be quantized. The choice of quantization can critically affect the accuracy of the similarity measurement and matching processes.
Number in
Color range Code Color Figure
330 < Average_hue (window) <= 30 0 Red 870
30 < Average_hue (window) <= 90 1 Yellow 871
90 < Average_hue (window) <= 150 2 Green 872
150 < Average_hue (window) <= 210 3 Cyan 873
210 < Average_hue (window) <= 270 4 Blue 874
270 < Average_hue (window) <= 330 5 Magenta 875
The feature-based code generation steps discussed above have been separated out as steps for clarity of presentation. However, these steps are combined to minimize the computation required to generate these feature codes. The feature extraction and coding process described above is one specific method of generating the feature codes. Depending on the kind of similarity metric being used, the feature extraction and coding process can be significantly different. The code representation mechanism and its efficiency in performing similarity measurements are not significantly affected by the coding scheme itself For example, one possible metric of similarity is the motion similarity of image sequences, that is, here video sequences are compared based on flow rather than color. Such a coding and similarity measurement scheme can be used within the frame work proposed in this invention (see R. Mohan, "Video Sequence Matching", cited above). Let us assume that rectangular regions are used for feature computation. Then once the set S of reference segments, the windowing parameters (w.sub.1, w.sub.2), the number of features M with the number of feature codes for each feature are selected and k.sub.max, the maximum number of key frames for the segments s.sub.i in S is computed, the dimensions of each of the M segment index tables are fixed. In FIG. 3, the hue feature for segment detection amounts to the following segment index table. The feature codes 320 along the negative z-axis 325 numbered by 350, 352, . . . , 359 are 0, 1, 2, . . . , 5. The domain codes 330 along the y-axis (335) numbered 340, 242 . . . , 349 are (0,0), (0,1), (0,2) . . . referring to the windows. The x-axes 310 of the table is the key frame number (time dimension). FIG. 9 gives an example of the use of the Fourier transform for computing feature codes for the audio track 902. (Note that the use of audio is not limited to the audio track of a video signal.) The audio signal, a function of time t 904, is partitioned into audio key intervals 905 (centered around t.sub.k --908), 906, . . . , etc. These intervals can be overlapping or non-overlapping and they can be regular spaced in time or irregular spaced in time. For each interval, in this case interval 905, the discrete Fourier transform 910 is computed which gives a discrete function, .vertline.F(s).vertline. 912, of frequency s, defined for s=0 (913) through s=s.sub.max (914). The frequency distribution .vertline.F(s).vertline. is only defined at a finite number of points 916 in the interval [0, s.sub.max ]. The frequency domain W=[0, s.sub.max ] is divided up into a set W (923) of regions w.sub.1, w.sub.2, . . . , w.sub.i, . . . , w.sub.N, (924, 925, . . . , 926) in order to compute the feature average A(W) 922 through the transformation 920. For each window w the average of the .vertline.F(s).vertline. with frequencies s in w is computed, for example, the average of .vertline.F(s).vertline. of window w.sub.2, 925, is A(w.sub.2), 927. Also to each window in W a domain code d is assigned, that is, in FIG. 9 w.sub.1 is associated with d.sub.1 (934), w.sub.2 is associated with d.sub.2 (935), . . . , and w.sub.N is associated with d.sub.N (936). This gives the domain codes D={d.sub.1, d.sub.2, . . . , d.sub.N } 933. The last step 930 is the computation of the feature codes 932 through transformation 930. The feature codes are a quantization of the range of the function .vertline.F(s).vertline. 912, i.e., a quantization of the interval [0, F.sub.max), where F.sub.max is the maximum amplitude of F. The feature codes C 932 are shown as c.sub.1, . . . , c.sub.j, . . . , C.sub.M (941, 942, . . . , 943) and map into some partitioning of the interval [0, F.sub.max), c.sub.1 is associated with [0, F.sub.1), c.sub.2 is associated with [0, F.sub.2), and so forth. Now for each domain code d, a feature code c is determined. In FIG. 9, the feature code for d.sub.2 935 is c.sub.j 942 because the quantization of A(w.sub.2) 927 is equal to c.sub.j 937. Hence, in summary the input is the audio stream S(t) 902 of FIG. 9 and for interval t.sub.k 908 the output is a set pairs ((d, e))=((d.sub.1, e.sub.1), (d.sub.2, e.sub.2), . . . , (d.sub.N, e.sub.N)). Here d.sub.1, d.sub.2, . . . , and d.sub.N are the doma codes D 933 and e.sub.1, e.sub.2, . . . , e.sub.N are elements of C={c.sub.1, c.sub.2, . . . , c.sub.M }, the set of feature codes. Intuitively, domain code c.sub.i refers to a frequency band, the corresponding window w.sub.i in [0, s.sub.max ], and the associated feature code e.sub.i is the average of the frequency distribution in band w.sub.i. The latter is related to the amount of energy (`amount of frequency`) in band w.sub.i. Hence, if the audio in interval 905 is of lower frequency, feature codes for the lower domain codes tend to be of higher value. Conversely, if the audio piece 905 contains high frequencies, the higher domain codes (higher frequencies) have higher feature codes. The domain and feature codes that are computed from a media interval are used to populate the segment index structure. There are several known different structures that may be used to store these codes, namely, a tree structure, a graph structure, a table structure, a linked list structure, etc. The index structures are a quantized representation of the media streams, where the media stream has been quantized in multiple dimensions, namely, time (through key-interval selection), domain (windowing for video, and frequency ranges for audio) and feature space (examples include, color, edges, motion vectors, etc.). Each of the index structures offers a some advantages. This embodiment of the invention uses a segment index table. This choice is motivated by, the following reasons, 1. Traversal of a table structure during search is computationally efficient. 2. The table structure is well suited for representation of temporal order. 3. The table structure is also suited for an inverted index representation. 4. The table structure provides a highly compressed searchable representation of the reference media streams. The index structures used in this invention provide an explicit representation of time. How ever this does not impose any temporal ordering on the target media stream for segments to be automatically recognized. The search algorithm which compares the target stream against the index structure can choose to recognize any number of variations in temporal ordering. The ability to recognize a temporal ordering of a reference segment, which may be different from the temporal ordering of the reference segment used to generate the index structure, is a very important functionality. One application of this functionality is in recognizing commercials which may be shortened from their original length. The prior art has not addressed this problem. Now, let there be N domain codes D=(d.sub.1, d.sub.2, . . . , d.sub.N) and M=10 feature codes C=(c.sub.1, c.sub.2, . . . , c.sub.M) and let s(k, i) be the k-th key interval in reference media segment s.sub.i. Then the set of code pairs for this interval can be as above ((d, e))=((d.sub.1, e.sub.1), (d.sub.2, e.sub.2), . . . , (d.sub.N, e.sub.N))=((d.sub.1, c.sub.3), (d.sub.2, C.sub.2), (d.sub.3, c.sub.5), (d.sub.4, c.sub.10), . . . , (d.sub.N, c.sub.1)), which is a compact representation of the segment interval. This can be represented in a two-dimensional table which codes the k-th key interval in reference media segment s.sub.i as follows. The table referred by T(k) contains only one entry per row--each domain code corresponds to one feature code, (not vice versa). This is Table I shown below. Let (k, j) denote the k-th key interval in reference media segment s.sub.j, this interval can similarly be represented by a string of code pairs ((d, e))=((d.sub.1, e.sub.1), (d.sub.2, e.sub.2), . . . , (d.sub.N, e.sub.N)). Given that the audio segment intervals (k, i) and (k, j) differ sufficiently and the feature values are sufficiently finely quantized into feature codes c.sub.1, c.sub.2, . . . , C.sub.N then the set of codes for these segments are different. The code pairs for instance, could be ((d, e))=((d.sub.1, c.sub.1), (d.sub.2, c.sub.2), (d.sub.3, c.sub.7), (d.sub.4, c.sub.4), . . . , (d.sub.N, c.sub.8). This can be added to the above table, resulting in the second table (Table II) below. Entry (2,2) contains both i and j, none of the other entries contain (or point to) both segment intervals k of the segments i and j. This means that for domain code 2, which corresponds to a frequency window w.sub.2 (925 in FIG. 9) the quantized average frequency is the same for both segment intervals. For all other frequency windows, or domain codes, the corresponding feature codes are different.
TABLE I
Segment index table T(k) for key interval k of s.sub.i.
d
c 1 2 3 4 N
1 i
2 i
3 i
4
5 i o o o
6
7
8
9
10 i
If the same computations as in FIG. 9 are performed for an audio interval M.sub.t of an unknown target audio stream M, a new string of code pairs ((d, e)) is the result. Then by checking the table entry contents ((d, e))=((d.sub.1, c.sub.1), (d.sub.2, c.sub.2), (d.sub.3, c.sub.7), (d.sub.4, c.sub.4), . . . , (d.sub.N, c.sub.8)) of the Table II, it can be determined if M.sub.t is similar to either of the two audio intervals. If many of the target code pairs of M.sub.t collide with the same reference audio interval, the target and reference interval are similar.
TABLE II
Segment index table T(k) for key interval k of s.sub.i and s.sub.j.
d
c 1 2 3 4 N
1 j i
2 i
j
3 i
4 j
5 i
6
7 j
8 j
9
10 i
None of the above is limiting to just audio segments or audio segment intervals. Any one and higher dimensional signal that is a function of time and is sampled in time, is a function of the integers, or is a function of some other countable set of numbers can be indexed in the above fashion. Refer to FIG. 10 which gives a flow diagram for filling the segment index table of FIG. 3 for a given key interval at some t=k, (k, i), hereafter referred to as reference segment # A (which can be one frame). The output of step 875 in FIG. 8A, is a list of pairs {(d.sub.i, e.sub.i), i=1, . . . , M}, with N the number domain codes and each e.sub.i, i=1, . . . , M a feature code value. Here d.sub.i is in D and e.sub.i is in C for each i=1, . . . , M and C={c.sub.i, i=1, . . . , N} the possible feature codes. Hence the segment index table is. an array of N rows and M columns. Let the segment index table be initialized to NIL. The domain codes for segment A, D=(d.sub.1, d.sub.2, . . . , d.sub.N) are stored in 1020 of FIG. 10 while the corresponding feature codes E=(e.sub.1, e.sub.2, . ., d.sub.M) are stored in 1030. The process starts at 1005 by initializing i to zero and immediately in step 1015 setting i to i+1. In 1020 a test is performed whether all the domain codes have been handled, in which case i is M+1 (1022) and the process terminates 1060. If in 1020 i is not equal to M+1 (1024), the process continues to step 1025. In this step, domain code d.sub.i is fetched from the domain code store 1020. Subsequently, in step 1035 the corresponding feature code e.sub.i is fetched from the feature code store 1030 which has been previously computed like in FIG. 8A and FIG. 9. Step 1040 finds the cell (d.sub.i, e.sub.i) in the feature index table (column d.sub.i and row e.sub.i) and finally segment # A is inserted in this cell. This indicates that for segment #A and key interval k the region corresponding to domain code d.sub.i resulted in a feature value which in quantized form corresponds to e.sub.i. The scheme of FIG. 10 only encodes one key interval and does not incorporate the time aspects of multiple key intervals. (Time can be omitted) or it can be incorporated into the segment index table in multiple fashions. Omitting the time aspects amounts to not recording the time t or order k of the key intervals of the reference media segments and hence not enforcing this ordering for segment detection in the target stream. Filling of the segment index table is very similar to the filling of table II above. Again, let there be N domain codes D={d.sub.1, d.sub.2, . . . , d.sub.N } and M=10 feature codes C=c.sub.1, c.sub.2, . . . , c.sub.10) and let i be any key interval in a reference media segment s.sub.i. Here we omit the k referring to the location of the key element. Then the set of code pairs for i might be ((d, e))=((d.sub.1, e.sub.1), (d.sub.2, e.sub.2), . . . , (d.sub.N, e.sub.N))=((d.sub.1, c.sub.3), (d.sub.2, c.sub.2), (d.sub.3, c.sub.5), (d.sub.4, c.sub.10), . . . , (d.sub.N, c.sub.1)). Another key interval of s.sub.i may have code pairs ((d.sub.1, C.sub.3), (d.sub.2, c.sub.2), (d.sub.3, C.sub.4), (d.sub.4, C.sub.8), . . . , (d.sub.N, C.sub.4)). These code pairs can be represented in the cells of the segment index table as in Table III below. For a key interval in another reference media segment s.sub.j, the code pairs could be ((d, e))=((d.sub.1, c.sub.1), (d.sub.2, c.sub.2), (d.sub.3, c.sub.7), (d.sub.4, C.sub.4), . . . , (d.sub.N, c.sub.8)). Any key element in reference segment s.sub.j is referred to by j and hence the appropriate cells in the segment index table are filled with j (Table III). This can be repeated for all key intervals in all s.sub.i, i=1, . . . , n in S, the set of reference segments.
TABLE III
Segment index table T for segments i and j without ordering.
d
c 1 2 3 4 N
1 j i
2 i, i, j
3 i, i
4 i j i
5 i o o o
6
7 j
8 i j
9
10 i
Two methods for incorporating time t or order k in the segment index tables will follow. Refer to the table 1000 in FIG. 10A. This is an alternative implementation of the preferred embodiment of the segment index table in FIG. 3. This two-dimensional segment table indexes domain, feature codes associated with all the key intervals k=1, 2, 3, . . . , k.sub.max and reference segments i andj. For instance, the first key interval of segment i (i.e., (1, i)) has code pairs (1, 3) 1032, (2, 2) 1035, (3, 5), (4, 8), . . . , and (N, 1) 1038. The second key interval of segment i (i.e., (2, i)) has code pairs (1, 1) 1042, (2, 4) 1045, (3, 1), (4, 3), . . . , and (N, 2) 1048. Hence cell (d, c) indexed by domain code d 1010 and feature code c 1020, contains a list of pairs (k, i) with k a key interval and i a reference segment. The cell (d, c) contains all key intervals where domain code is d and feature code is c for any of the segments s.sub.i. Or, in other words, if for reference segment i the domain, feature code pair is (d, c) for the kth key interval, cell (d, c) of the table will contain the pair (k, i). So if for reference segment i, domain code 3 of the first key interval has feature code 5, cell (3,5) 1025 will contain (1, i). Similarly, if for reference segment i, domain code 3 of the second key interval has feature code 5, cell (3,5) 1025 will also contain (2, i). Each individual column 3030 of the reference segment table in FIG. 10A is associated with a domain code d which in turn refers to the same region in all key intervals. Since for every such region in every key interval a feature code is computed (FIG. 8A and 8B), every key interval k=1, 2, 3, . . . , k.sub.max and every reference segment s.sub.i, i=1, 2, . . . , n (in FIG. 10A reference segments i an j) is represented. For each column 1030, every key interval k and every reference media stream identifier i the pair (k, i) is represented only once since with each domain code there is only one feature code associated. Turn now to FIG. 10B. Here a segment index table 1500 is shown that essentially contains the same information as the table in FIG. 10A. The columns of the table refer to domain codes 1010, while the rows refer to feature codes. But rather than using one two-dimensional for all the key intervals as in FIG. 10A, the segment index table of FIG. 10B allocates a two-dimensional array to each of the key intervals 1155. That is, the first two-dimensional array 1054 is allocated to key interval 1, the second array 1058 to key interval 2, and so on. The cells of the first array 1054 contain all the information of the segment index table of FIG. 10A that pertains to the first key interval. For example, the first key interval of segment i (i.e., (1, i)) has code pairs (1, 3) 1032, (2, 2) 1035, (3, 5), (4, 8), . . . , and (N, 1) 1038. The second key interval of segment i (i.e., (2, i)) has code pairs (1, 1) 1042, (2, 4) 1045, (3, 1), (4, 3), . . . , and (N, 2) 1048. Hence, for each array k, for kth key interval, cell (d, c) indexed by domain code d 1010 and feature code c 1020, contains a subset of reference segment identifiers S'={i, j, . . . }. This means that the feature code for domain d of the kth key interval of the reference segments in S' is equal to c. Hence, if for reference segment i the domain, feature code pair is (d, c) for the kth key interval, the cell (d, c) in the kth array of the segment index table will contain segment identifier i. Each individual column 1030 of each individual array in FIG. 10B is associated with a domain code d which in turn refers to the same region in the key interval represented by that array. Since for every such region in every key interval a feature code is computed (FIG. 8A and 8B), every key interval k=1, 2, 3, . . . , k.sub.max and every reference media segment s.sub.i, i=1, 2, . . . , n (FIG. 10B reference segments i an j) is represented. For each column 1030 and every reference media stream identifier i, the identifier is represented only once since with each domain code there is only one feature code associated. An example of media segment recognition is searching (scanning) a target media stream for know media segments. That is, a target media stream M (for example, a TV channel, VTR output, MPEG1 or MPEG2 or AVI or Real Video streams) is compared to the known set of reference media segments S. The goal is to recognize the occurrence of any of the known segments (reference segments) of S in the target stream M. The output of the recognition process will be a set of triplets (identity i of the segment, temporal location of the match within the segment s.sub.i and temporal location within the target media stream M). This is the index report 185 in FIG. 1. Since the target media stream is a continuous, the frames from the target media streams will have to be processed sequentially in time, while maintaining a temporal history of the matching results. The following table shows some of the symbols used in the discussion of the segment recognition process.
M target media stream in which the reference media streams
are to be recognized
S set of reference media segments to be indexed, this is the
set of known media segments
s.sub.i reference media segment with identifier i
v.sub.i number of votes received by the reference segment number i
T segment index table
Ot time offset into the target media stream
Os time offset into the reference segment
Otb beginning time offset for a section of the target
media stream
Ote end time offset for a section of the target media stream
Osb beginning time offset for a sub-segment of the reference
media segment
Ose end time offset for a sub-segment of the reference
media segment
k.sub.max length of segment index table (maximum number of
key intervals)
L.sub.H length of history table
The architecture of the search engine (e.g., 165 in FIG. 1) is described in FIG. 11A. The target media stream M (1101) on channel 160 can exist in a variety of media and formats. For example, the target media stream may be an analog media stream in NTSC or PAL format or it may be a digital media stream in MPEG1 or MPEG2 format. The search engine is designed to deal with any of these formats. The general philosophy of the search process is to transcode the media into a common format. Typically all formats of media have a decoder algorithm (publicly available) which outputs 24 bit RGB frames for video and pcm format audio, since these are the formats used to render the audio and video on a computer monitor. The search algorithm operates on this common format. In FIG. 11, the incoming media stream 1101 could potentially be in any format like NTSC/PAL 1103, MPEG1/MPEG2 1109, AVI 1113, some arbitrary format xxx 1119 or Real Video 1123. Depending on the format of the media, it is processed through the corresponding decoder, NTSC/PAL 1103 through the frame grabber hardware 1107, MPEG1/MPEG2 through the MPEG Decoder 1111, AVI 1113 through the AVI Decoder 1117, some unknown format xxx 1119 through the corresponding decoder 1121, and Real Video 1123 through the Real Video Decoder 1127. The output of each of the decoders in FIG. 11A will be some generic video frame format like RGB or YIQ 1129. The segment search algorithm operates on this 1129 data. The segment search algorithm 1133 uses the segment index table 1131, populated by the process described in FIG. 10, and the decoded target media stream 1129 to generate the search results 185, named the index report 185 in FIG. 1. The details of the search algorithm are discussed in FIGS. 11B, 12 and 13. The process of recognizing a reference segment within a t second target stream M segment 1101 using a segment index table T is described in FIG. 11B. The segment index table T is generated by populating it with domain-feature code pairs as described in FIG. 10. The domain and feature codes are derived from the reference media segments S (110 in FIGS. 1 and 2). Time running from time 0 to time t seconds is indicated by the time axis 1107. For efficiency purposes a subset of key intervals M may be selected. The key intervals from target stream M are selected by the key interval counter Ot, the first key interval to be processed is the key interval at the start of M, Ot=Oo 1110, subsequent key intervals arc spaced by key interval increment Odelta, that is, Ot=Ot+Odelta 1115. The recognition or search process has three major steps, 1130 is the step which generates the domain and feature codes for the present key interval Ot of the target media stream M 1101. In block 1150 these codes are used to select the L most similar key intervals of the reference segments S 110 (described in FIG. 12). Block 1170 keeps track of these matches provided by 1150 over multiple key intervals in the target stream. Block 1170 also uses this tracking information to delineate a start-time and end-time in the target media stream M for the matching subintervals of the reference segments S and declare the results of the search process, the index report 185 in FIG. 11B (described in FIG. 13). As stated above, step 1110 initializes the key interval counter Ot to the desired start position Oo, typically the first key interval of media stream M. Here the key interval increment Odelta is initialized to the number of key intervals by which the media M should be advanced each processing cycle. This value is typically set to one (one key interval for video media or audio media). Step 1130 is the code generation process for the selected key interval in the target media stream at offset Ot. In the case of video media one possible code generation process (hue codes) has been described in FIG. 8A. In the case of audio media one possible code generation process (frequency content) has been described in FIG. 9. However, any code generation process resulting from some region transformation 406, FIG. 4A, or media transformation, 417, FIG. 4B, may be used here. The result of this code generation process is shown in 1140. It comprises the relative time offset into the target media where the code generation occurred, Ot, the set of target domain codes extracted at that point and the corresponding set of target feature codes that is, ((d, c))=((d.sub.1, c*), (d.sub.2, c*), (d.sub.3, c*), (d.sub.4 c*), . . . , (d.sub.N, c*)). Here c* is any c in C={c.sub.t, i=1, . . . , N}, the possible target feature codes. Step 1150 performs the process of taking the domain and feature codes 1140 and searching for matches in the segment index table T. A detailed description, indicated by A 1155, of the steps performed within step 1150 is given in FIG. 12. The result of the search process is the winner table 1160. This comprises, a list of top L key intervals of the reference segments that best match the target media key interval under consideration (at Ot). Step 1170 takes the winner table as input, accumulates the results over multiple key intervals Ot and produces the index report, shown in 185 in FIG. 11B. The result comprises the R different reference segments s.sub.r, r=1, . . . , R to which a particular section [Oth, Ote] of the target media stream M matches (we refer to it as `section` to distinguish it from reference segments and key intervals). For each potential match, the sub segment [Osbr, Oser ] within the reference segment s.sub.r which matches and the number of votes it polled are also part of the index report 185. The number of results R declared at each target media stream offset Ot, cart vary from 0 to n, where n is the number of reference segments in set S represented in the segment index table T. Typically, in an application like detecting commercials in a live TV feed, R will be 0 most of the time (during program blocks) and will be 1 at sections [Otb, Ote] of M where known commercials are inserted. Once the results of matching at offset Ot are computed, step 1190 checks for the end of the media stream. This step is applicable only in the case of disk based media like MPEG video files or MP3 audio files. In the case of streaming media like TV feeds there is no physical end of the media. In case the end of media has been reached, the processing stops 1195. If the end of the media stream has not been reached, the target media stream M 1105 is advanced by Odelta as shown in 1115. FIG. 12 describes the process of searching the segment index table T (1150 of FIG. 11). The code pairs (shown as 1235 in FIG. 12), ((d, c))=((d.sub.1, c*), (d.sub.2, c*), (d.sub.3, c*), (d.sub.4, c*), . . . , (d.sub.N, c*)) computed from M at some time offset Ot 1140 from FIG. 11 are used as the input to the search process. That is, the code pairs are used to index the segment index table T. The process in FIG. 12 finds the closest P reference segment key intervals to target key interval Ot tabulated in the winner table 1255. The process in FIG. 12 begins at 1200, which is a connection to reference segment search (1155 of FIG. 11). The first step in the search process is 1205, which sets the range of reference segment key intervals to be searched in the segment index table. Os is the offset (measured in key intervals) into the index table at which the search begins, End is the offset at which the search ends and Delta is the incremental offset between search cycles. Typically Os would be set to 0 and End would be set to k.sub.max (length of the segment index table, the maximum number of key intervals found in the reference segments). This ensures that all the key intervals in the segment index table are matched against each of the key intervals extracted from the target media stream. This setting ensures the recognition of a target media stream that contains any sub segment of the reference media stream. The search range can be altered each time a new key interval from the target media is being matched. Thus, the search space in the segment index table can be dynamically pruned (for example, once the leading portion of a reference segment has been detected, further searches could be performed against later portions of the segment index table). Such a pruning strategy is applicable for applications where the target stream includes the reference segment streams in their entirety without any modifications. Implementation of this, and other, search pruning strategies are obvious to those skilled in the art. Using the complete table for all searches (no dynamic pruning), on the other hand, allows for recognition of target stream sections which are composed of multiple sub-segments of one or more reference segments in random temporal order. Step 1220 uses the segment index table 1215 and the domain code, feature code pairs ((d, c)) pairs 1235 (which are the same as 1140 in FIG. 11) to generate a hit list. For every domain, feature code pair (d.sub.n, c*), n=1, . . . , N this step generates a hit-list from the segment index table. The hit list h.sub.n corresponding to code (d.sub.n, c*) is a list of reference segment identifiers, a subset of S. It is the set of reference segments which have the same domain code d.sub.n and feature code at offset Os as the target stream M at Ot. The cardinality of h.sub.n can be anywhere between 0 and the cardinality of S (total number of reference segments). The hits generated by the domain, feature codes ((d, c)) are given by H=(h.sub.1, h.sub.2, h.sub.3 . . . h.sub.N). In fact, every domain code d.sub.n gives a hit list h.sub.n, 1225 shows the hits the domain code and the corresponding hit list obtained from the segment index table. In summary, the output 1225 of 1220 is a count of how key interval Os of the various reference segments S fit the target stream key interval Ot. Each domain d.sub.n in the target key interval generates a hit list, that is, the reference segments for which at Os and domain d.sub.n the feature code equals the feature code of the target key interval. Step 1230 uses the hit list H generated by 1220 to accumulate hits in the score table (1225). The score table is a two-dimensional table of size (End.times.n). In this step, for each member of the hit list H (these members are reference segment identifiers) at offset O.sub.s (this is always between 0 and End), the corresponding cell in the score table (1225) is incremented by 1. Thus the score table accumulates the hits against each reference segment identifier i=1, . . . , n and reference segment key interval Os. With H the union of (h.sub.1, h.sub.2, h.sub.3 . . . h.sub.N), the (Segment ID, Os) cell will contain t count of segment s.sub.i with i=SegmentID in H. Step 1240 compares the current offset in the segment index table Os to the end of the search range End. If the search is within the specified range (Os<End) the offset is incremented in step 1245 by Delta and the search process described above repeats at the new offset. If the offset is outside the specified range (Os=End), the search process ends. Once the end of search interval End is reached, the results in the score table are processed in step 1250. The entries of score table 1225 contain votes for (i, Os) pairs, with i a segment identifier. These entries are sorted in the descending order of the votes polled by each reference segment i at each of its key intervals Os. The votes in the sorted list are compared against a threshold 1260. All the entries in the sorted list that are below the vote threshold are removed from the list. After the thresholding operation, the top P items in the list are selected and output into the winner table, 1255. The winner table now lists for key interval Ot of the target stream which reference segment key interval Os1 of all key intervals in S fits best, which reference key interval Os2 of all key intervals in S fits second best, and so on. Hence we have an ordering of (reference segments, key interval) pairs. P is the number of similarly entries that are tracked over time. The winner table 1255, has the following entries, the order number p, p=1, . . . , P, the reference segment identifier s.sub.p, the number of votes v.sub.p polled for this reference segment, the offset (key interval) Osp at which these votes were polled and the target segment offset Ot that caused these matches. The winner table 1255 is used in the history and segmentation process 1170 of FIG. 11B. The detailed description of 1170 is provided in FIG. 13. Connector 1260 in FIG. 12 is used as the start 1305 of FIG. 13. FIG. 13 describes the vote history accumulation and segmentation steps (1170 of FIG. 11A). The connector 1305 in FIG. 13 comes from connector 1260 in FIG. 12. Step 1320 takes entries from the winner table (1255 of FIG. 12) and merges these in the history table, 1310 (at Ot=Oo, the history table is initialized as the winner table) The history table (1310) acts as a cache for a fixed number of search results. The result of the past H searches (winner tables) can be cached in the history table. That is, the last H target stream interval matches at Oth, h=1, . . . , H to reference segment intervals are merged into the history table 1310. The length of the table, formed by merging H winner tables is L.sub.H =H. The history table allows for identifying coherent segments 1330 by detecting contiguous target key interval offsets, Ot3, Ot4, Ot4, that are associated with contiguous segment key intervals Os1, Os2, Os3. The table also allows for filtering of spurious hits which exhibit themselves by gaps in the contiguous Oti, Osj pairs. Spurious hits can occur because of changes in the media characteristics caused by different encoding parameters (bit-rates, frame sizes in the case of video, varying sampling rates, recording levels and channel composition in the case of audio), noise introduced by acquisition devices (frame grabbers and microphones) and several other factors. Mismatches can also potentially occur due to the coding process. Also potentially, one target media stream section can match sub-segments of multiple reference media streams. Step 1330 filters the history table based a several different filtering criteria, like minimum number of contiguous hits on a segment and temporal ordering of the hits. The thresholds used for these operations need to be chosen based on the application. For example in the case of detecting commercials in a live TV feed, the minimum number of contiguous hits required would be 3 matching frames. This translates to a clip of video 0.1 sec's long, (1/10 second.times.30 frames/second=3 frames). The output of step 1330 is the index report 185. The result comprises of R matching entries, the number of sub-segmelts of reference segments in S that match some section in target stream M. Each entry in the result table comprises, the matching reference stream identifier r element of S, the begin-time and end-time offsets Otbr and Oter of the matching section in the target media stream M, the begin-time and end-time offsets Osbr and Oser into the reference stream s.sub.r, and the number of votes v.sub.r. Step 1350 compares the number of entries in the history table to the length of the history table L.sub.H. If the table is full it clears the oldest (first) entry in the history table. After this operation the control flows via 1380 to 1180 in FIG. 11. If the end of the target media stream is not reached, the target media is advanced and the search continues (as described in FIG. 11). Application of the Invention We list a number of applications that are hard or impossible to achieve with prior art technology. The following is a business method and method of use that is detailed and claimed in U.S. patent application Ser. No. 09/496,928, entitled BUSINESS METHOD AND METHOD OF USE FOR MEASURING SIMILARITY BETWEEN A SET OF KNOWN TEMPORAL MEDIA SEGMENTS AND A ONE OR MORE TEMPORAL MEDIA STREAMS, with the same inventorship, filed on the same day as this disclosure, and that is herein incorporated by reference in its entirety. A first application is monitoring a given television or radio broadcast for the occurrence of instances of a pre-specified set of media segments. Such broadcast monitoring can be used to detect any type of pre-produced media material. The more typical use is for verifying the broadcasting of TV or radio commercial messages (advertisements). Advertisers (companies whose products are being advertised) require an independent verification of the actual broadcasting of the commercial in order to make payments to the broadcaster. This process currently relies on a human viewer sampling the channel to verify the airing of a commercial. Hence, it is a labor intensive and error prone process. The similarity measurement process described in this invention can be used to serve the function of the human viewer. The commercial messages to be monitored is a set reference media streams S. As described in this invention, these reference media streams are used to generate an index representation called a segment index table (T-commercial). To monitor a given channel, Channel X, (a target media stream) for commercials, a computing system that houses the search engine described in this invention is used. Depending on the type of broadcast (National Television System Committee (NTSC), Phase Alternating Line (PAL), digital, analog/digital audio), the media source (tuned to Channel X) is decoded and input to the computing system. The search engine operates on the target media stream and produces an index report. This index report, in the case of commercial monitoring, will include the title of the commercial detected (reference segment identifier), the date and time at which the commercial started, the date and time at which the commercial ended and the match quality (the votes it received). The same apparatus can be used to perform quality control operations on the commercials (reference media streams) that are being monitored. In this case, the index report will include a list of offsets into the recognized reference media stream, if any, at which the match qualities (number of votes received) were below an acceptable threshold. Locating copies of media on the Internet is another application of the present invention. This application involves searching for digital copies of media (audio or video) on the Internet. With the wide spread use of digital media (audio and video), the illegal copying and distribution of media are emerging as a significant problem for the media industry. For example, there are a number of web sites that post illegal copies of music and video on the Internet. The media is encoded in one of the popular formats (MP3 for audio; MPEG1 or MPEG2 for video). Typically, the filenames under which the media is posted, are not indicative of the content of the media files. To identify a posted media file (MP3 or MPEG) as a known media stream, a comparison of the media content of the file (video or audio key intervals) is necessary. The search method described in this invention can be used to perform the comparison. In this case, the media streams of interest (say several movies) are used as the reference media segments to generate a representation called the segment index table (T-movie). The search engine is now deployed with the segment index table (T-movie). The target media files are transferred from web sites at the Internet to the computing system that houses the search engine described in this invention. That is, the media needs to be downloaded or streamed to the machine on which the search engine is running. The downloading operation can be achieved in multiple ways, an operator could feed URL's to down loader software, which would download the files to the local machine or alternatively, a web crawler robot could be designed to locate URL's that hold media files. This can be done by looking at the filename extensions (.mp3, .mpeg, etc). The URL's located by the crawler robot or human operator can be filtered based on various criteria, like size of the media files, to generate a list of URL's for downloaded software. Once a target media stream has been downloaded to the local machine the search engine is deployed to generate an index report. This application provides functionality similar to video water marking in that the search engine detects the intrinsic properties (features) of the media instead of the embedded water marks. An application of the present invention targeted towards the task of video indexing is video event detection. Video indexing can be defined as the operation of designating video segments with certain predefined labels. There exists a significant body of prior art on the subject of video indexing. For example, consider a video of a soccer game, indexing this video will result in annotation table that looks as follows
Event Number Begin Time End Time Label
1 00:00:10:12 00:00:12:10 Penalty Kick
2 00:20:12:10 00:20:13:10 Field Goal
3 00:33:12:09 00:35:12:10 Penalty Corner
4 . . . . . . . . .
There are several approaches to generating such indices, using software algorithms, described in the prior art. One of the approaches to event detection has been disclosed in R. Mohan. This approach uses reference video segments (examples of how a typical event would look like) and compares the target stream to the reference video segment based on generating codes for both the reference segment and the target segment. The discussion provided by Mohan however does not address the problem of performing such similarity measurements between a target stream and a multiplicity (large number) of reference streams. Essentially, the target stream is simultaneously compared to the reference segments in a sequential fashion, one reference segment at a time. This inherently limits the number of reference segments that can be used in the comparisons. The similarity search method discussed in this invention can be applied to the video event detection problem as follows. The multiple example videos for the events to be detected are selected. These videos form the reference media streams S. The reference media streams are used as input to the index generation process. In this process, the motion similarity codes discussed by Mohan are extracted from the reference segments. These codes are used to populate a segment index table (T-event). The search engine described in this invention is deployed with this segment index table (T-event). The target media stream (the video to be annotated) is fed to the appropriate decoder and the search engine operates on the target media stream to generate the index report. This index report is a tabulation of the events in the target stream as shown in the table above. This event detection is not limited to off-line video annotation, but also can be performed in real-time. Applications are in the arena of surveillance, monitoring and human machine interaction. Events, such as, dangerous situations, human gestures, etc. Can be detected in real time by employing the search engine described in this invention with an appropriate segment index table. The present invention can be employed in the management of large audio and video databases. Such collections of audio or video clips need to be managed and searched in several environments like TV news, documentary, movie and sitcom productions. In these production environments, audio and video segments in the database will be used to produce program material, often the same media segment in different productions. It is important to keep track of the usage of a media segment from the perspective of rights management and royalty payments. The similarity measurement method discussed in this invention can be used in this process. In this case, the index generation phase and the search phase operate repeatedly in sequence. The following steps outline the usage of the similarity measurement method in video database indexing and management. Every media item (s) which is entered into the database is first used as target media stream and searched against the segment index table of the database (T-database). This operation generates an index report. (In the case of the very first video item entered into the database, this step will be skipped and the entire item will be used as the reference media stream and inserted into the segment index table, T-database.) Based on the index report, the segments of the media item (s) that are unique (no matches were reported in the index report) are used as reference media streams for the index generation process, which adds the corresponding codes to the segment index table (T-database). The index report is stored along with the database and used to keep track of the content usage. As per the above procedure, the segment index table will continually grow as more and more media items are added to the database. Once, the database of media is indexed in terms of content usage, several tasks, like removing redundant copies of the video, selecting all videos that contain a specified segment, etc., are straightforwardly accomplished. The present invention can also be used for detecting patterns in non signal data streams. One such application is in computer virus detection. Here the known computer virus patterns are treated as the reference streams. The reference virus patterns are used to generate a virus index structure. The search for viruses will use the data taken from the hard disk as the target stream. The search engine matches the target stream against the index table and identifies portions of the target stream which are close matches to the viruses.
|
Same subclass Same class | ||||||||||