Abstract:
A motion detection method determines bit-rate changes of input pixels of a video frame by a grey relational analysis technique to establish a multi-quality background model, detects moving objects by two-stage block-based and pixel-based detection procedures to generate a binary motion mask, detects luminance changes of the video frame by entropy calculation to timely update the background model, provides a setting interface for a user to set a detection sensitivity, and examines false detections of the binary motion mask. Therefore, it can correctly interpret moving objects in VBR video streams, implement more accurate and complete motion detection, eliminate the influence of luminance changes, increase the detection accuracy, and decrease false detections.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to an image processing method and, more particularly, to a motion detection method for extracting information regarding moving objects from video streams. 
     2. Description of the Related Art 
     Motion detection is a key technique used in automatic video surveillance systems to extract information regarding moving objects from video streams. Motion detection methods can be divided into three major categories: temporal difference, optical flow, and background subtraction methods. Temporal difference method is easy to implement, and calculated amount is little; however, it very often generates holes inside moving objects and inevitably extracts incomplete shapes of moving objects. Optical flow method can extract complete shapes of moving objects and can detect moving objects when the camera is moving; however, it is not suitable for real-time applications due to large calculated amount and sensitive to noise. Background subtraction method is easy to implement and can extract reasonable information regarding moving objects with moderate calculated amount by using background models under a relatively static background; however, it is extremely sensitive to luminance changes. Therefore, background subtraction methods have been popularly used in motion detection applications, and various types of background subtraction methods such as Gaussian mixtures model (GMM), sigma difference estimation (SDE), multiple SDE (MSDE), multiple temporal difference (MTD), and simple statistical difference (SSD) methods have been developed. 
     With recent advances in video communication technology, wireless communication has become more viable for motion detection applications as a way to enhance measurement capabilities in a wide range of detection of moving objects. Unfortunately, wireless communication is especially prone to network congestion and server crashes due to the bandwidth constraints of real-world networks. In response, a video rate control technique has been introduced in video streams such as H.264/AVC video format which supports variable-bit-rate (VBR) encoding to adapt real-world network conditions. The aforementioned conventional background subtraction methods can detect moving objects in video streams which have fixed bit rates. In such an ideal, stable environment, moving objects are easily distinguished by the background models of these methods. However, because real-world networks rarely offer an ideal, stable environment, the aforementioned conventional background subtraction methods possibly misinterpret moving objects when the bit rate suddenly changes, and effective detection of moving objects in VBR video streams is a very difficult problem for these methods. 
     For example, referring to  FIG. 6 , there is illustrated a diagram showing luminance values of pixels at the same position of several video frames in a VBR video stream. In the beginning at the 150 th  video frame, the video stream has a high bit rate of 200 kbps and has a strong, fluctuant (or high-quality) background signal B 1  accordingly. The conventional background subtraction methods generate background models according to the strong, fluctuant background signal B 1 . When video communication is hindered by network congestion, the video rate control technique allocates the remaining network bandwidth, and subsequently, at the 240 th  video frame, the video stream becomes to have a low bit rate of 5 kbps and have a smooth (or low-quality) background signal B 2  with a strong, fluctuant motion signal P 1  due to a passing moving object. If the motion signal P 1  is present while the background model is not yet updated (that is, still generated according to the strong, fluctuant background signal B 1 ), the conventional background subtraction methods possibly misinterpret the motion signal P 1  as a background signal. After a period of time, the background model is updated according to the smooth background signal B 2 . However, when video communication is not hindered at the 280 th  video frame, the video stream is restored to have a high bit rate of 200 kbps and have a strong, fluctuant (or high-quality) background signal B 3 . If the background signal B 3  is present while the background model is not yet updated (that is, still generated according to the smooth background signal B 2 ), the conventional background subtraction methods possibly misinterpret the background signal B 3  as a motion signal. Therefore, the conventional background subtraction methods possibly misinterpret when the bit rate of video streams changes from high to low, or from low to high. 
     SUMMARY OF THE INVENTION 
     The present invention is adapted to providing a motion detection method, which can correctly interpret moving objects in VBR video streams to implement more accurate and complete motion detection, and can eliminate the influence of luminance changes. 
     According to an aspect of the present invention, there is provided a motion detection method based on grey relational analysis. The motion detection method includes the following steps: S 1 ) receiving a video frame including a plurality of input pixels; S 2 ) establishing a multi-quality background model; S 3 ) detecting moving objects; S 4 ) detecting luminance changes of the video frame; S 5 ) examining false detections of the binary motion mask. 
     Moreover, the step of S 2  includes: S 21 ) calculating a Euclidean distance between a pixel value of each input pixel and a pixel value of each of a plurality of corresponding candidate background pixels; S 22 ) according to the Euclidean distances, calculating a grey relational coefficient between the pixel value of each input pixel and the pixel value of each of the corresponding candidate background pixels; S 23 ) for each input pixel, determining whether the minimum value of the grey relational coefficients is smaller than or equal to a first threshold value; if yes, determining that a bit rate of the input pixel has been changed, and the input pixel is regarded as a new candidate background pixel accordingly; if no, determining that the bit rate of the input pixel is not changed. 
     Moreover, the step of S 3  includes: S 31 ) dividing the video frame into a plurality of blocks, and for each block, summing up the maximum values of the grey relational coefficients between the pixel value of each input pixel and the pixel values of the corresponding candidate background pixels within the block to generate a grey relational coefficient sum regarding the block; S 32 ) determining whether the grey relational coefficient sum is larger than or equal to a second threshold value; if yes, determining that the block is a background block; if no, determining that the block is a motion block; S 33 ) for each input pixel within each motion block, determining whether the maximum value of the grey relational coefficients between the pixel value of each input pixel and the pixel values of the corresponding candidate background pixels is larger than or equal to a third threshold value; if yes, determining that the input pixel is a background pixel; if no, determining that the input pixel is a motion pixel; S 34 ) generating a binary motion mask. 
     Moreover, the step of S 4  includes: S 41 ) calculating an entropy of the grey relational coefficient sum of each block, and summing up the entropies of the grey relational coefficient sums of the blocks to generate an entropy sum regarding the video frame; S 42 ) determining whether a difference between the entropy sum of the video frame and an entropy sum of a previous video frame is larger than or equal to a fourth threshold value; if yes, determining that the video frame has luminance changes, and updating a candidate background pixel corresponding to each input pixel according to the video frame; if no, determining that the video frame has no luminance changes. 
     Moreover, the step of S 5  includes: S 51 ) providing a setting interface for a user to set a detection sensitivity; S 52 ) dividing a total number of the motion pixels and the background pixels of the binary motion mask by an area of the binary motion mask to generate an examination value; S 53 ) determining whether the examination value is larger than a product of a fifth threshold value and the detection sensitivity, wherein a prediction number of true positive pixels divided by the area of the binary motion mask is the fifth threshold value; if yes, determining that there are false detections; if no, determining that there are no false detections. 
     The motion detection method determines bit-rate changes of the input pixels by the grey relational analysis technique to establish the multi-quality background model, and therefore can correctly interpret moving objects in VBR video streams. The motion detection method further detects moving objects by two-stage detection procedures (i.e. block-based and pixel-based detection procedures) to generate the binary motion mask, and therefore can implement more accurate and complete motion detection. The motion detection method further detects luminance changes of the video frame by entropy calculation to timely update the background model, and therefore can eliminate the influence of luminance changes. The motion detection method further provides the setting interface for the user to set the detection sensitivity with higher values meaning higher detection accuracy, and examines false detections of the binary motion mask; therefore, it can increase the detection accuracy and decrease false detections. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention will be described in further detail below under reference to the accompanying drawings, in which: 
         FIG. 1  is a flow chart of a motion detection method based on grey relational analysis according to a preferred embodiment of the invention; 
         FIG. 2  is a flow chart of a method for establishing a multi-quality background model according to a preferred embodiment of the invention; 
         FIG. 3  is a flow chart of a method for detecting moving objects according to a preferred embodiment of the invention; 
         FIG. 4  is a flow chart of a method for detecting luminance changes of a video frame according to a preferred embodiment of the invention; 
         FIG. 5  is a flow chart of a method for examining false detections of a binary motion mask according to a preferred embodiment of the invention; and 
         FIG. 6  is a diagram showing luminance values of pixels at the same position of several video frames in a VBR video stream. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to  FIG. 1 , there is illustrated a flow chart of a motion detection method based on grey relational analysis according to a preferred embodiment of the invention. In a step S 1 , the motion detection method receives a video stream including a plurality of video frames. Each video frame includes a plurality of input pixels. For convenience of distinction and explanation, the t th  video frame is notated as I t , and an input pixel at a position (x,y) of the t th  video frame I t  is notated as p t (x,y). In the embodiment, the motion detection method is implemented in a YC b C r  color space, and each input pixel p t (x,y) has a corresponding color or pixel value represented by three variables: a luminance value (Y), a blue-difference chroma value (C b ), and a red-difference chroma value (C r ). In addition, each of the luminance value (Y), the blue-difference chroma value (C b ), and the red-difference chroma value (C r ) can be represented by 8 bits with values of 0 to 255. 
     In a step S 2 , the motion detection method determines bit-rate changes of the input pixels by the grey relational analysis technique to establish a multi-quality background model. In the embodiment, referring to  FIG. 2 , there is illustrated a flow chart of a method for establishing a multi-quality background model according to a preferred embodiment of the invention. In a step S 21 , the method calculates a Euclidean distance Δ between a pixel value of each input pixel p t (x,y) and a pixel value of each of a plurality of corresponding candidate background pixels B(x,y) 1  to B(x,y) M . The Euclidean distance Δ can be expressed for each input pixel p t (x,y) as follows:
 
Δ( k )=∥ p   t ( x,y )− B ( x,y ) k ∥
 
where k is an integer ranging from 1 to M, and M is the number of corresponding candidate background pixels. Because the motion detection method is implemented in the YC b C r  color space, each candidate background pixel B(x,y) k  has a corresponding color or pixel value represented by three variables: a luminance value (Y), a blue-difference chroma value (C b ), and a red-difference chroma value (C r ). The longer Euclidean distance Δ(k) indicates the larger difference between the input pixel p t (x,y) and the candidate background pixel B(x,y) k , whereas the shorter Euclidean distance Δ(k) indicates the smaller difference between the input pixel p t (x,y) and the candidate background pixel B(x,y) k .
 
     In a step S 22 , the method calculates, according to the Euclidean distances Δ( 1 ) to Δ(M), a grey relational coefficient γ between the pixel value of each input pixel p t (x,y) and the pixel value of each of the corresponding candidate background pixels B(x,y) 1  to B(x,y) M . The grey relational coefficient γ can be expressed for each input pixel p t (x,y) as follows: 
               γ   ⁡     (         p   t     ⁡     (     x   ,   y     )       ,       B   ⁡     (     x   ,   y     )       k       )       =         Δ   min     +     ξ   ⁢           ⁢     Δ   max             Δ   ⁡     (   k   )       +     ξ   ⁢           ⁢     Δ   max                 
where k is an integer ranging from 1 to M, Δ min  represents the minimum difference, and Δ max  represents the maximum difference. Because each of the luminance value (Y), the blue-difference chroma value (C b ), and the red-difference chroma value (C r ) is represented by 8 bits with values of 0 to 255, Δ min  and Δ max  can be set to 0 and 255, respectively. In addition, ξ represents a distinguishing coefficient ranging from 0 to 1, and in the embodiment, ξ is set to 0.2. The smaller grey relational coefficient γ(p t (x,y), B(x,y) k ) indicates the lower correlation (i.e. the larger difference) between the input pixel p t (x,y) and the candidate background pixel B(x,y) k , whereas the larger grey relational coefficient γ(p t (x,y), B(x,y) k ) indicates the higher correlation (i.e. the smaller difference) between the input pixel p t (x,y) and the candidate background pixel B(x,y) k .
 
     In a step S 23 , the method determines, for each input pixel p t (x,y), whether the minimum value of the grey relational coefficients γ(p t (x,y), B(x,y) 1 ) to γ(p t (x,y), B(x,y) M ) is smaller than or equal to a first threshold value ε. If yes, it indicates that there is substantially no correlation between the input pixel p t (x,y) and the candidate background pixels B(x,y) 1  to B(x,y) M , and the method goes to a step S 231  accordingly. In the step S 231 , the method determines that a bit rate of the input pixel p t (x,y) has been changed, and a bit-rate-change indication V k  of the input pixel p t (x,y) is labelled as ‘1’. Moreover, the input pixel p t (x,y) can be regarded as a new candidate background pixel. If no, it indicates that there is very higher correlation between the input pixel p t (x,y) and some candidate background pixel, and the method goes to a step S 232  accordingly. In the step S 232 , the method determines that the bit rate of the input pixel p t (x,y) is not changed, and the bit-rate-change indication V k  of the input pixel p t (x,y) is labelled as ‘0’. By doing so, the multi-quality background model can be flexibly established in the VBR video stream. The bit-rate-change indication V k  can be expressed for each input pixel p t (x,y) as follows: 
               V   k     =     {           1   ,       if   ⁢           ⁢     min   ⁡     (     γ   ⁡     (         p   t     ⁡     (     x   ,   y     )       ,       B   ⁡     (     x   ,   y     )       k       )       )         ≤   ɛ                 0   ,   otherwise                   
where k is an integer ranging from 1 to M, and the first threshold value ε can be empirically set to 0.6.
 
     Referring again to  FIG. 2 , in a step S 3 , the motion detection method detects moving objects by two-stage detection procedures (i.e. block-based and pixel-based detection procedures) to generate a binary motion mask. In the embodiment, referring to  FIG. 3 , there is illustrated a flow chart of a method for detecting moving objects according to a preferred embodiment of the invention. The block-based detection procedure includes steps S 31 , S 32 , S 321 , and S 322 . In the step S 31 , the method divides the video frame I t  into a plurality of blocks M(i,j). In the embodiment, according to MacroBlock types supported by H.264 video encoding, the video frame I t  is divided into 16×16 blocks M( 1 , 1 ) to M( 1 , 16 ), M( 2 , 1 ) to M( 2 , 16 ), . . . , and M( 16 , 1 ) to M( 16 , 16 ), which are notated as M( 1 , 1 ) to M( 16 , 16 ) hereinafter; in other words, i and j of M(i,j) are integer ranging from 1 to 16. For each block M(i,j), the method sums up the maximum values of the grey relational coefficients γ(p t (x,y), B(x,y) 1 ) to γ(p t (x,y), B(x,y) M ) between the pixel value of each input pixel p t (x,y) and the pixel values of the corresponding candidate background pixels B(x,y) 1  to B(x,y) M  within the block M(i,j) to generate a grey relational coefficient sum S(i,j) regarding the block M(i,j). The grey relational coefficient sum S(i,j) can be expressed for each block M(i,j) as follows: 
               S   ⁡     (     i   ,   j     )       =       ∑       p   t     ∈     M   ⁡     (     i   ,   j     )           ⁢     max   ⁡     (     γ   ⁡     (         p   t     ⁡     (     x   ,   y     )       ,       B   ⁡     (     x   ,   y     )       k       )       )               
where k is an integer ranging from 1 to M.
 
     In the step S 32 , the method determines whether the grey relational coefficient sum S(i,j) is larger than or equal to a second threshold value α. If yes, it indicates that the block M(i,j) is not a motion block, and the method goes to the step S 321  accordingly. In the step S 321 , the method determines that the block M(i,j) is a background block, and a motion block indication R(i,j) of the block M(i,j) is labelled as ‘0’. If no, it indicates that many input pixels p t (x,y) within the block M(i,j) are parts of moving objects, and the method goes to the step S 322 . In the step S 322 , the method determines that the block M(i,j) is a motion block, and the motion block indication R(i,j) of the block M(i,j) is labelled as ‘1’. The motion block indication R(i,j) can be expressed for each block M(i,j) as follows: 
               R   ⁡     (     i   ,   j     )       =     {           0   ,       if   ⁢           ⁢     S   ⁡     (     i   ,   j     )         ≥   α                 1   ,   otherwise                   
where the second threshold value α can be experimentally set to  245 .
 
     The pixel-based detection procedure includes steps S 33 , S 331 , S 332 , and S 34 . In the step S 33 , for each input pixel p t (x,y) within each motion block, the method determines whether the maximum value of the grey relational coefficients γ(p t (x,y), B(x,y) 1 ) to γ(p t (x,y), B(x,y) M ) between the pixel value of each input pixel p t (x,y) and the pixel values of the corresponding candidate background pixels B(x,y) 1  to B(x,y) M  is larger than or equal to a third threshold value β. If yes, it indicates that there is very higher correlation between the input pixel p t (x,y) and some candidate background pixel, and the method goes to the step S 331  accordingly. In the step S 331 , the method determines that the input pixel p t (x,y) is a background pixel. If no, it indicates that there is substantially no correlation between the input pixel p t (x,y) and the candidate background pixels B(x,y) 1  to B(x,y) M , and the method goes to the step S 332  accordingly. In the step S 332 , the method determines that the input pixel p t (x,y) is a motion pixel. Next, in the step S 34 , the method generates a binary motion mask BM which can be expressed as follows: 
               BM   ⁡     (     x   ,   y     )       =     {           0   ,       if   ⁢           ⁢     max   ⁡     (     γ   ⁡     (         p   t     ⁡     (     x   ,   y     )       ,       B   ⁡     (     x   ,   y     )       k       )       )         ≥   β                 1   ,   otherwise                   
where k is an integer ranging from 1 to M, and the third threshold value β can be empirically set to 0.6.
 
     Referring again to  FIG. 2 , in a step S 4 , the motion detection method detects luminance changes of the video frame by entropy calculation to timely update the background model. In the embodiment, referring to  FIG. 4 , there is illustrated a flow chart of a method for detecting luminance changes of a video frame according to a preferred embodiment of the invention. In a step S 41 , the method calculates an entropy of the grey relational coefficient sum S(i,j) of each block M(i,j) via the entropy formula—S(i,j)log(S(i,j)), and sums up the entropies regarding the blocks M( 1 , 1 ) to M( 16 , 16 ) to generate an entropy sum E t  regarding the video frame I t . The entropy sum E t  can be expressed as follows: 
     
       
         
           
             
               E 
               t 
             
             = 
             
               - 
               
                 
                   ∑ 
                   
                     
                       ( 
                       
                         i 
                         , 
                         j 
                       
                       ) 
                     
                     ∈ 
                     
                       I 
                       t 
                     
                   
                 
                 ⁢ 
                 
                   
                     S 
                     ⁡ 
                     
                       ( 
                       
                         i 
                         , 
                         j 
                       
                       ) 
                     
                   
                   ⁢ 
                   
                     log 
                     ⁡ 
                     
                       ( 
                       
                         S 
                         ⁡ 
                         
                           ( 
                           
                             i 
                             , 
                             j 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
     In a step S 42 , the method determines whether a difference between the entropy sum E t  of the video frame I t  and an entropy sum E t-1  of a previous video frame I t-1 , i.e. |E t −E t-1 |, is larger than or equal to a fourth threshold value μ. If yes, it indicates that the video frame I t  has sudden luminance changes, and the method goes to a step S 421 . In the step S 421 , the method determines that the video frame I t  has luminance changes, and a luminance-change indication L t  is labelled as ‘1’. If no, the method goes to a step S 422  to determine that the video frame I t  has no luminance changes, and the luminance-change indication L t  is labelled as ‘0’. The luminance-change indication L t  can be expressed as follows: 
               L   t     =     {           1   ,       if   ⁢           ⁢            E   t     -     E     t   -   1                ≥   μ                 0   ,   otherwise                   
where the fourth threshold value μ can be empirically set to 0.05. Furthermore, in the step S 421 , because the method determines that the video frame I t  has luminance changes, it can update a candidate background pixel B(x,y) s  corresponding to each input pixel p t (x,y) according to the video frame I t  as follows:
 
 B ( x,y )′ s   =B ( x,y ) s +ρ( p   t ( x,y )− B ( x,y ) s )
 
where B(x,y) s  represents a candidate background pixel at a position (x,y) which will be updated, B(x,y)′ s  represents a updated candidate background pixel at the position (x,y), and ρ represents a default parameter. The candidate background pixel B(x,y) s  which will be updated can be chosen from a candidate background pixel corresponding to the maximum value of the Euclidean distances Δ( 1 ) to Δ(M). The candidate background pixel B(x,y) s  which will be updated can be expressed as follows:
 
     
       
         
           
             
               
                 B 
                 ⁡ 
                 
                   ( 
                   
                     x 
                     , 
                     y 
                   
                   ) 
                 
               
               s 
             
             = 
             
               arg 
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   max 
                   
                     k 
                     = 
                     
                       1 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       to 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       M 
                     
                   
                 
                 ⁢ 
                 
                   Δ 
                   ⁡ 
                   
                     ( 
                     k 
                     ) 
                   
                 
               
             
           
         
       
     
     Referring again to  FIG. 2 , in a step S 5 , the motion detection method provides an adjustable detection sensitivity and examines false detections of the binary motion mask BM. In the embodiment, referring to  FIG. 5 , there is illustrated a flow chart of a method for examining false detections of a binary motion mask according to a preferred embodiment of the invention. In a step S 51 , the method provides a setting interface for a user to set the detection sensitivity ds. For example, the setting interface is a graphical user interface having a bar with a slide, and the detection sensitivity ds can be adjusted from 0 to 10. The higher detection sensitivity ds indicates the higher detection accuracy, whereas the lower detection sensitivity ds indicates the lower detection accuracy 
     In a step S 52 , the method divides a total number n dp  of the motion pixels and the background pixels of the binary motion mask BM by an area of the binary motion mask BM to generate an examination value E BM . The examination value E BM  can be expressed as follows: 
               E   BM     =       n   dp       dim   ⁢           ⁢   X   ⁢           ⁢   dim   ⁢           ⁢   Y             
where n dp =p p +p n , p p  represents the number of the motion pixels of the binary motion mask BM, p n  represents the number of the background pixels of the binary motion mask BM, and dimX and dimY represent the width and the height of the binary motion mask BM, respectively.
 
     In a step S 53 , the method determines whether the examination value E BM  is larger than a product of a fifth threshold value δ and the detection sensitivity ds, wherein a prediction number Ω of true positive pixels divided by the area of the binary motion mask BM is the fifth threshold value δ. The fifth threshold value δ can be expressed as follow: 
             δ   =     Ω     dim   ⁢           ⁢   X   ⁢           ⁢   dim   ⁢           ⁢   Y             
If yes, E BM &gt;δ×ds, and the method goes to a step S 531 . In the step S 531 , the method determines that there are false detections in the binary motion mask BM, and a fault alarm indication F is labelled as ‘1’. If no, E BM ≦δ×ds, and the method goes to a step S 532 . In the step S 532 , the method determines that there are no false detections in the binary motion mask BM, and the fault alarm indication F is labelled as ‘0’. The fault alarm indication F can be expressed as follows:
 
             F   =     {           1   ,       if   ⁢           ⁢     E   BM       &gt;     δ   ×   ds                   0   ,   otherwise                   
where the prediction number Ω of true positive pixels can be experimentally set to 30×30.
 
     It will be apparent to those skilled in the art that various modifications and variations can be made to the structure of the present invention without departing from the scope or spirit of the present invention. In view of the foregoing, it is intended that the present invention cover modifications and variations of this invention provided they fall within the scope of the following claims and their equivalents.