Abstract:
A viewer-intuitive index may be built from a stream of video data by detecting scene changes from the stream of video data, capturing reference markers associated with the video data for those portions of the video data for which the scene changes were detected and the storing the reference markers.

Description:
BACKGROUND 
     The present invention relates to a scene change detector for video data. 
     In most video applications, it is difficult for viewers to navigate through video content in an intuitive manner. A viewer may desire to browse through video content by fast-forwarding or rewinding through it. However, most video data is indexed by a time scale or a frame counter. Because viewers typically do not think in terms of elapsed time or elapsed frames, such indices are not helpful to permit a viewer to quickly identify and select desired subject matter. 
     Lay users of conventional domestic videocassette recorders may be familiar with this phenomenon when they desire to watch portions of a favorite movie. Often, to reach a desired portion of a movie, it is necessary to fast-forward or rewind the cassette for an arbitrary period of time then play the cassette to determine at what point in the plot the cassette has reached. The “fast-forward, then play” operation is repeated in essentially a hit-or-miss fashion until the viewer has reached the desired portion of the movie. Of course, many conventional video cassette recorders display a running count of elapsed time or elapsed frames while a cassette is fast forwarding. Nevertheless, the “fast-forward, then play” operation is used because viewers do not intuitively correlate elapsed time or frames to video content. 
     Certain other video applications, for example the later-generation digital video discs and the MPEG-4 video-coding standard, may permit video content publishers to provide semantic information to accompany the video data. Such semantic information, conceivably, could support an index to the information content within the video data. However, in such instances, viewers would be able to use such an index only if the video publisher deigned to create one. Further, particularly in the MPEG-4 example, such semantic information consumes precious bandwidth that the coding standard was designed to conserve. 
     Accordingly, there is a need in the art for a video application that permits viewers to browse and access video data in an intuitive manner. Further, there is a need for such an application that generates an index to the video information based upon the content of the video information and without consuming the communication bandwidth of the video data signal itself. 
     SUMMARY 
     Embodiments of the present invention provide a method of building an index of a stream of video data, in which scene changes are detected from the stream of video data, reference markers associated with the video data are capture for those portions of the video data for which the scene changes were detected and the reference markers are stored. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates an exemplary video data stream. 
     FIG. 2 illustrates a scene change detector according to an embodiment of the present invention. 
     FIG. 3 illustrates a method of operation according to an embodiment of the present invention. 
     FIG. 4 illustrates a scene change detector according to another embodiment of the present invention. 
     FIG. 5 illustrates a video processing device according to an embodiment of the present invention. 
     FIG. 6 illustrates a video processing device according to another embodiment of the present invention. 
     FIG. 7 illustrates a computer system that may be applied with embodiments of the present invention. 
    
    
     DETAILED DESCRIPTION 
     Embodiments of the present invention provide a scene change detector for video data. The scene change detector compares pixel data for several consecutive frames, identifies covered and uncovered pixel data therefrom and, depending upon the number of covered and uncovered pixels, determines that a scene change has occurred. 
     FIG. 1 illustrates four consecutive frames of video data  10 - 40  for display. Each frame is populated by a number of picture element (“pixel”) locations. Thus, the video data typically is represented by pixel data, at least one pixel coefficient representing the information content of a respective pixel location. The frames of video data  10 - 40  relate to video information at an arbitrary present time t, and previous times t−1, t−2 and t−3. 
     FIG. 2 illustrates a scene identifier  100  according to an embodiment of the present invention. The scene identifier  100  may be populated by a pair of pixel classifiers  110 ,  120  and a scene change identifier  130 . Each pixel classifier  110 ,  120  in turn may be populated by a pair of comparators  140 - 150 ,  160 - 170 , a pair of slicers  180 - 190 ,  200 - 210  and a pixel classifier  220 ,  230 . 
     The pixel classifiers  110 ,  120  each compare video data of three video frames and generate pixel classifications therefrom. The first pixel classifier  110  receives video information from video frames t through t−2 and identifies covered and uncovered pixels therein. The second pixel classifier  120  receives video information from video frames t−1 through t−3 and identifies covered and uncovered pixels therein. The results of the covered/uncovered classification are output from each of the first and second pixel classifiers  110 ,  120  to the scene change identifier  130 . From those results, the scene change identifier  130  determines whether a scene change has occurred in the video data. 
     The present invention identifies that a scene occurs at a frame t when there is an abrupt change in value at a large number of pixels for the frame t when compared to the pixels of temporally adjacent frames and when the succeeding frames exhibit relative stability. As may be appreciated by a lay observer, a scene change typically involves a complete change of displayed information content at one discrete frame but, after the scene change occurs, the succeeding frames exhibit relative stability. By contrast, other phenomena may cause a large change in displayable content (such as when a camera pans). Although, these phenomena may cause a dynamic change in displayable content from frame-to-frame, they typically do not exhibit marked stability among ensuing frames. Embodiments of the present invention exploit this difference between scene changes and other phenomena. 
     Accordingly, embodiments of the present invention identify a scene change in a frame t by comparing pixel values among the frame t and a plurality of temporally contiguous frames (for example, frames t−1 through t+2). When there is a high dynamic change in scene content from frame t−1 to frame t and where there is a relatively low change in scene content from frame t through, say, frame t+2, a scene change is detected. 
     According to the present invention, pixel data from a series of frames may be analyzed to identify “covered” and “uncovered” data in a series of temporally contiguous frames. Each pixel classifier (say, pixel classifier  110 ) performs a pair of comparisons from three frames (e.g., frame t vs. frame t−1 and frame t−1 vs. frame t−2). The comparison may make on a pixel-by-pixel basis. 
     Consider the pixel classifier  110  for example. There, a first comparator  140  receives pixel data for a first and second video frame (frames t and t−1). For each pixel in a first video frame (t), the comparator  140  determines a difference between the pixel and a corresponding pixel from the second video frame (t−1). The comparator  140  outputs a signal representing a difference between the pixels of the two frames (Δp x,y ). 
     The slicer  180  performs threshold detection upon the output from the comparator  140 . For those pixels where the Δp x,y  signal exceeds a predetermined threshold, the slicer  180  outputs a binary signal in an active state (e.g., “ON”). For those pixels where the Δp x,y  signal does not exceed a predetermined threshold, the slicer  180  may output a binary signal in a second state (e.g., “OFF”). 
     Thus the first comparator  140  and first slicer  180  generate a binary signal for each pixel location in a video display representing the magnitude of the difference between pixel values in frames t and t−1. The binary output of the slicer  180  may be labeled Q 1   x,y . 
     The second comparator  150  and the second slicer  190  may operate in a similar manner but on different inputs. The second comparator receives pixel data from video frames at times t−1 and t−2 and generates a differential signal therefrom. The second slicer  190  generates a binary signal representing the magnitude of the differential signal. Thus, for each pixel in a video frame, the second comparator  150  and the second slicer  190  outputs a binary signal, labeled Q 2   x,y  representing the change in video data at the pixel location. 
     The classifier  220  compares the output signals from each slicer  180 ,  190  in the first pixel classifier  110 . Each pixel location will be associated with a Q 1 -Q 2  pair. The Q 1 -Q 2  values determine whether the pixel is covered or uncovered as shown in the following table: 
     
       
         
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Pixel State (Q1) 
                 Pixel State (Q2) 
                 Classification 
               
               
                   
               
             
             
               
                 OFF 
                 OFF 
                 — 
               
               
                 OFF 
                 ON 
                 Covered 
               
               
                 ON 
                 OFF 
                 Uncovered 
               
               
                 ON 
                 ON 
                 — 
               
               
                   
               
             
          
         
       
     
     Thus, for each pixel in the video display, the pixel classifier  110  outputs a signal identifying whether the pixel is covered, uncovered or neither covered nor uncovered. 
     According to an embodiment of the present invention, the second pixel classifier  120  may be constructed similarly to the first pixel classifier  110 . The second pixel classifier  120  may receive video data from a series of three video frames, the series delayed by one frame with respect to the video inputs to the first pixel classifier  110 . Thus, where the first pixel classifier  110  receives video data from frames t, t−1 and t−2, the second pixel classifier  120  may receives video data from frames t−1, t−2 and t−3. 
     The second pixel classifier  120  may include first and second comparators  160 ,  170 . The first comparator  160  may receive video data from frames t−1 and t−2 and generates a differential signal therefrom on a pixel-by-pixel basis. The first slicer  200  receives the output from the first comparator  160 , compares the output to a predetermined threshold and generates a binary signal Q 1  therefrom. 
     The second comparator  170  may receive video data from frames t−2 and t−3 and generates a differential signal therefrom on a pixel-by-pixel basis. The second slicer  210  receives the output from the second comparator  170 , compares the output to a predetermined threshold and generates a binary signal Q 2  therefrom. The Q 1  and Q 2  outputs from the two slicers  200 ,  210  are input to a classifier  230 . 
     For each pixel in the video display, the second pixel classifier  120  outputs a signal identifying whether the pixel is covered, uncovered or neither covered nor uncovered. 
     The scene change identifier  130  receives the outputs from the first and second pixel classifiers  110 ,  120  and generates a signal identifying whether a scene change has occurred. 
     FIG. 3 illustrates a method of operation of the scene change identifier according to an embodiment of the present invention. According to such embodiment, for one frame, the scene change identifier  130  counts the number of uncovered pixels identified by the first pixel classifier  110  (step  1010 ) and the number of covered pixels identified by the first pixel classifier  120  (step  1020 ). Similarly, the scene change identifier  130  counts the number of uncovered and covered pixels identified by the second pixel classifier  120  for one frame (steps  1030 ,  1040 ). 
     The scene change identifier  130  may perform a series of threshold tests upon the output from the two pixel classifiers  110 ,  120  to determine whether a scene change has occurred. If the output data fails any of the threshold tests, it is determined that no scene change occurred (Step  1050 ). If the output data passes all of the threshold tests, then a scene change has occurred (step  1060 ). 
     A first threshold test determines whether the ratio of covered to uncovered pixels identified by the first pixel classifier  110  exceeds a predetermined threshold, labeled TH 1  (step  1070 ). If not, then there can be no scene change. 
     A second threshold test determines whether the number of uncovered pixels identified by the first pixel classifier  110  exceeds a second predetermined threshold, labeled TH 2  (step  1080 ). 
     A third threshold test determines whether the number ratio of covered to uncovered pixels from the second pixel classifier exceeds a third predetermined threshold, labeled TH 3  (step  1090 ). According to an embodiment, the first and third predetermined thresholds may be set to the same value (e.g. TH 1 =TH 3 , in an embodiment). 
     A fourth threshold test determines whether the number of uncovered pixels identified by the second pixel classifier  120  exceeds a fourth predetermined threshold, labeled TH 4  (step  1100 ). According to an embodiment, the second and fourth predetermined thresholds may be set to the same value (e.g., TH 2 =TH 4 , in an embodiment). 
     According to an embodiment of the present invention, the thresholds TH 1 -TH 4  each may be programmable thresholds. By allowing user control of such thresholds, it permits a viewer to adjust the sensitivity of the scene change detector  100  to changes in video content. 
     FIG. 4 illustrates a scene change detector  200  constructed in accordance with another embodiment of the present invention. There, the scene change detector  200  generates a binary scene change signal in response to video content of four frames, such as the frames  10 - 40  shown in FIG.  1 . As compared to the scene change detector  100  of FIG. 2, the scene change detector  200  possesses a more efficient design. 
     A review of FIG. 2 demonstrates that the first and second pixel classifiers  110 ,  120  each duplicate a portion of the other&#39;s processing. The data path formed by comparator  150  and slicer  190  performs the identical processing as the data path formed by comparator  160  and slicer  200 . In the embodiment of FIG. 4, such redundancy is eliminated. 
     FIG. 4 illustrates a scene change detector  200  that is populated by three comparators  210 - 230 , three slicers  240 - 260 , a pair of classifiers  270 - 280  and a scene change identifier  290 . Each of the comparators  210 - 230  determines the differences between two consecutive video frames on a pixel-by-pixel basis. Comparator  210  generates a differential signal based upon video frames  10 ,  20  at times t and t−1. Comparator  220  generates a differential signal based upon video frames at times t−1 and t−2. Comparator  230  generates a differential signal based upon video frames at times t−2 and t−3. The slicers  240 - 260  each generate a binary ON/OFF signal based on the outputs of the respective comparators  210 - 230 . 
     The classifier  270  receives the outputs from slicers  240  and  250  as inputs. The output from slicer  240  is received as a Q 1  input, the output from slicer  250  is received as a Q 2  input. Using these inputs, the classifier  270  generates an output signal according to the scheme identified in Table 1 above. 
     The second classifier  280  receives the outputs from slicers  250  and  260  as inputs. The output from slicer  250  is received by the second classifiers  280  as a Q 1  input, the output from slicer  260  is received as a Q 2  input. Using the inputs, the second classifier  280  generates an output signal according to the scheme identified in Table 1 above. 
     According to an embodiment, the scene change identifier  290  may operate in accordance with the method  1000  of FIG.  3 . 
     Thus, the scene change detector  200  of FIG. 4 provides a more efficient system for detecting scene changes from a video stream than would the scene change detector  100  of FIG. 2 by eliminating certain redundancies. Those of skill in the art will appreciate, however, that the structure of FIG. 2 may be easier to implement in certain circumstances. By way of example, if the scene change detectors  100  and  200  were implemented in software running on a general purpose processor, it may be easier to write a single software routine to perform the functions of a pixel classifier  110  or  120 . In such an example, this single software routine may be run twice—once to act as the first pixel classifier  110  and a second time to act as the second pixel classifier  120 —each time using different input data. Thus, both embodiments of the scene change identifier  100 ,  200  have certain advantages that depend upon the application for which they will be used. 
     FIG. 5 illustrates a video processing system  300  constructed in accordance with an embodiment of the present invention. The video processing system  300  may use a scene change detector  310  to build an index of a video stream that is based upon scenes. This index could later be used for the video browsing features described above. 
     The embodiment of FIG. 5 is appropriate for use with data streams that carry their own timing references in the data stream. As is known, in certain video applications such as the MPEG-4 coding standard for motion pictures include timing references embedded as administrative information within same data stream that carries the video data itself. Such timing references may be expressed in terms of an elapsed time for the data stream or as a frame count, by way of example. In such an embodiment, the video processing system  300  builds an index using the embedded timing references. 
     In the embodiment of FIG. 5, the video processing system  300  may include not only a scene change identifier  310  but also a controller  320 , a memory  330  and a plurality of delay stages  340 - 360 . The video processing system  300  also may include an input terminal  370  for input video data and an output terminal  380  for the video data. Note that the input and output terminals  370 ,  380  are shown as the same node. In this embodiment, the video processing system  300  is shown as a system that operates in parallel with the propagation of video data through a larger video processing system. In this embodiment, the video processing system  300  imposes no delay upon the video data and does not alter the video data in any way. 
     The scene change detector  310  receives input video data for the four frames at times t, t−1, t−2 and t−3. The delay stages  340 - 360  each provide a one frame delay to the input video data. The delay stages are interconnected in a cascaded manner so that the data output from delay buffer  360  (and input to the t−3 terminal of scene change detector  310 ) have passed through all three delay buffers  340 - 360 . The data output from delay buffer  350  is input to the delay buffer  360  and to the t−2 terminal of the scene change detector  310 . The data output from delay buffer  340  is input to the delay buffer  350  and also to the t−1 terminal of scene change detector  310 . And, finally, the t terminal of the scene change detector  310  is coupled directly to the input terminal  370 . The scene change detector  310  generates a binary output in response to these inputs. 
     The output from the scene change detector  310  is input to the controller  320 . In response to a detected scene change from the scene change detector  310 , the controller  320  captures the embedded timing information from the data at input terminal  370  that is associated with the video data at time t. The controller  320  stores this information in a memory  330 . 
     The video processing system  300  builds a scene-by-scene index of the video data based on the information content of the video data itself. 
     FIG. 6 illustrates another embodiment of a video processing system  400 . This second embodiment is appropriate for use in applications where the data stream carrying the video data does not carry timing information embedded therein. For example, conventional video cassettes carry no timing information thereon. 
     The video processing system  400  may be populated by a scene change detector  410 , a controller  420 , a memory  430  and a plurality of delay stages  440 - 460 . The scene change detector  400  also includes an input terminal  470  for the input of video data and an output terminal  480 . As with the video processor system  500  of FIG. 5, the video processing system  400  of FIG. 6 may be included in a larger video rendering system (not shown) and need not impede or alter the propagation of video data in the larger system. 
     The video processing system  400  may work with a reference counter  490  that supplies a timing reference for the video data. The reference counter  490  may be provided by the video processing system  400  or may be part of the larger video rendering system. For example, many domestic video cassette recorders include a timing circuit that counts elapsed running time of a cassette while playing. The video processing system  400  need not supply its own reference counter  490  but rather simply may interface with this timing circuit to obtain a timing reference for the video data. In other applications, it may be necessary to supply a reference counter  490  within the video processing system  400 . The reference counter  490  may count elapsed time or, alternatively, may count a number of elapsed frames to obtain a timing reference. 
     The output from the scene change detector  410  is input to the controller  420 . In response to a detected scene change from the scene change detector  410 , the controller  420  captures a timing reference from the reference counter  490 . The controller  420  stores this information in a memory  430 . 
     Thus, the video processing system  400  builds an scene-by-scene index of the video data based on the information content of the video data itself. 
     One of the advantages of the present invention is that it is able to build the index of scenes in a computationally fast manner. The subtractions, threshold tests and table look-ups that are performed by these embodiments are relatively simple. Thus, the invention may be performed in parallel with other conventional real-time processing that is associated with video processing with little or no performance degradation. 
     FIG. 7 illustrates a computer system  500  that may be adapted to function according to embodiments of the present invention. The computer system  500  may include a central processing unit (CPU)  510  or, alternatively, a digital signal processor or application specific integrated circuit (not shown). The computer system  500  further may include a memory  520 . The memory  520  may store executable instructions in a first portion thereof  522  to be executed by the CPU  510 . The memory  520  also may include volatile and non-volatile memory portions  524 ,  526  for storage of the index generated by certain embodiments of the present invention and for use during video processing according to the methods recited herein. According to an embodiment, the memory  520  may be populated by electrical, magnetic or optical memory devices. 
     According to an embodiment of the present invention, the video data upon which the processes described herein are operative may be stored in the memory  520  or may be received by the computer system  500  via an optional input/output device  530 . The input output device may any interface between the computer system and a video source. Accordingly, the input/output device may include a network interface to a larger computer network such as the Internet, an interface to another video communication such as a cable or satellite television system, or to some peripheral device over which video data may be communicated. 
     Several embodiments of the present invention are specifically illustrated and described herein. However, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.