Abstract:
A method and system for recognizing scene changes in digitized video is based on using one-dimensional projections from the recorded video. Wavelet transformation is applied on each projection to determine the high frequency components. These components are then auto-correlated and a time-based curve of the autocorrelation coefficients is generated. A decision is made to define a “scene change” when the autocorrelation coefficient curves are greater than a predetermined value.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims priority to Application No. 60/129,090, filed Apr. 13, 1999. 
    
    
     TECHNICAL FIELD 
     The present invention relates to a method for analyzing video frames and, more particularly, to a time-based evolution method of detecting scene changes in a video. 
     BACKGROUND OF THE INVENTION 
     The automatic analysis of video based on its content has applications in indexing and retrieval of visual information. In particular, the ability to automatically recognize a “scene change” in a video can be used to provide a useful index based on scene identity. Previous methods of automatically recognizing a “scene change” are based on defining a feature, or a “dissimilarity measure”, between two frames. When the dissimilarity measure is “high”, the two frames are defined as belonging to different scenes. A quantitative method of defining a “high” dissimilarity measure (usually through defining threshold values) is then the basis for defining a scene change. Various prior art algorithms have used histograms, motion and contour information for the features that are studied. A detailed analysis of various prior art approaches to determining scene changes can be found in the article entitled “Scene Break Detection: A Comparison”, by G. Lupatini et al. appearing in the  Proceedings of the Workshop on Research Issues in Data Engineering”,  1998, at pp. 34-41. 
     Many prior art approaches use techniques such as motion estimation and contour detection and attempt to determine “instant” values to define scene changes. The applied algorithms are based on a two-dimensional analysis of the video, are relatively complex and time-consuming to apply on an on-going basis. 
     Thus, a need remains in the art for a relatively simple, yet accurate method of detecting scene changes in recorded video. 
     SUMMARY OF THE INVENTION 
     The need remaining in the prior art is addressed by the present invention, which relates to a method for analyzing video frames and, more particularly, to a time-based evolution method of detecting scene changes in a video. 
     In accordance with the present invention, a video scene change is defined by creating one-dimensional projections of the video frames. At each spatial location, the time evolution of the one-dimensional projection is considered as a signal and the wavelet transform is calculated. At each time, therefore, the wavelet transforms are one-dimensional signals that can be used to define the high frequency components of the original video. The autocorrelation functions of the high frequency components are then calculated and used as features for scene change detection. 
     In one embodiment, the time evolution of the one-dimensional features can be displayed as curves. Scene change detection is accomplished by analyzing the shape of the curve. 
     Other and further features of the present invention will become apparent during the course of the following discussion and by reference to the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Referring now to the drawings, 
     FIG. 1 contains a block diagram of the scene change detection system of the present invention; and 
     FIG. 2 illustrates an exemplary implementation of a wavelet transform function. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 illustrates an exemplary system  10  of the present invention for detecting video scene changes. As mentioned above, prior art systems utilizes two-dimensional video analysis (contour changes, for example) that may be complicated and time-consuming to analyze. In contrast, the arrangement of the present invention uses only one-dimensional signals, evaluating these as a function of time to define scene changes. Referring to FIG. 1, system  10  includes a projection device  12  which is responsive to the incoming video. Projection device  12  derives one-dimensional signals from the video, in this case defined as a “column” (vertical) projection and “row” (horizontal) projection. 
     For the purposes of the present invention, it is presumed that the two-dimensional visual characteristic of the nth video frame (for example, intensity or color) is represented by A n (x,y), where x is the row index and y is the column index (the video is presumed to be digitized). To reduce the complexity of the video, projection device  12  creates row projection P x (n) and column prqjection P y (n) using the following formulas: 
     
       
           P   x ( n )=Σ y   A   n ( x,y ) 
       
     
     
       
           P   y ( n )=Σ x   A   n ( x,y ), 
       
     
     where P x (n) and P y (n) are considered as one-dimensional temporal signals. 
     The row and column one-dimensional projection outputs from projection device  12  are then applied as inputs to a pair of wavelet transformers  14   y  and  14   x , column projection P y (n) applied as input to wavelet transformer  14   y  and row projection P x (n) applied as an input to wavelet transformer  14   x . In general, at each spatial location, the time evolution of a projection (either row or column) is considered and the wavelet transform calculated. In particular, the premise behind a wavelet transform is to decompose the input signal (in this case, the projection) into two components: (i) a low-resolution approximation; and (ii) a detail signal. That is, the projection is decomposed into low-pass and high-pass components, generally referred to as subbands. 
     FIG. 2 illustrates in detail an exemplary wavelet transformer  14 , transformer  14  performing both decomposition and reconstruction of the applied input signal. The input to transformer  14  (such as the column projection P y (n)) is first applied, in parallel to a pair of finite impulse response (FIR) filters  20 , 22 , where filter  20  is defined by the function h(n) and filter  22  is defined by the function g(n). Filters  20 , 22  are followed, respectively, by down-samplers  24  and  26 . At this point, the one-dimensional input projection has been decomposed into the two components. Reconstruction is accomplished by first up-sampling the components, using a pair of samplers  28 ,  30 , then using complementary finite impulse response filters  32 , 34 , where filter  32  is defined by the function h and filter  34  is defined by the function g. In one embodiment of wavelet transformer  14 , a “delayed” wavelet transform function may be used. In this case, instead of using P(n), P(n+1), P(n+2), . . . to calculate the n th  wavelet coefficient, the series P(n), P(n+d), P(n+2d), . . . , where d is the delay. 
     In any embodiment of the present invention, the output of interest from wavelet transformers  14  is the high frequency component of the projection. Referring back to FIG. 1, the output from each wavelet transformer  14  is subsequently applied as an input to an associated spectral analyzer  16 , which performs an autocorrelation function of the high frequency component to define the “feature” that is ultimately evaluated to define a “scene change”. In particular, the m th  autocorrelation coefficient of a stationary real random process X(n) is defined as r(m)=E[X(n−m)X(n)], m=0, 1, 2, . . . . If the conditions of the ergodic theorem hold, the autocorrelation coefficients can be calculated using “ensemble averages” instead of the expectations as defined above. In this case, therefore, the autocorrelation function can be defined as follows: 
     
       
           r ( m )=Σ n   x ( n−m ) x ( n ), m= 0,1,2, . . .  
       
     
     The autocorrelation function outputs from spectral analyzers  16   y  and  16   x  are then applied to a decision module  18  which utilizes these definitions of “features” to determine if a scene change has occurred. In particular, the time evolution of the autocorrelation functions are analyzed and the average intensity is evaluated. For example, the first autocorrelation coefficients of a delayed wavelet transform (i.e., the high frequency subbands) of the projections are reviewed. When a scene change occurs, the general shape of the curve resembles a pulse with a width d. To capture such a pulse, the autocorrelation coefficients are valued at times n−2, n−1, n, n+1, n+2, . . . , n+d, n+d+1. In general terms, the values at times n, n+1, n+2, . . . , n+d−1 must be relatively “high” and the values at times n−2, n−1, n+d, n+d+1 must be relatively “low”. Such a behavior may be captured by comparing these d+4 values with each other and with “adaptive thresholds” that are calculated based on the history of the curves. 
     A subset of “scene changes” in general is defined as a “fade”. A fade may be detected based on two phenomena in the behavior of the collected data. First, a strong maximum in the autocorrelation coefficient curves (the general definition of a “scene change” coupled with a flat minimum in the average intensity curve. In general, however, any strong maximum in the autocorrelation coefficient curves can be used in accordance with the present invention to define a scene change.