Abstract:
A system, computer program product and associated methodology for video motion detection combines a series of images of a video sequence into an image volume having vertices of X, Y and t. The image volume is sliced in either the (X,t) or (Y,t) planes, filtered with a spatio-temporal filter and thresholded to reduce the amount of information. Then a search algorithm searches along search lines in a subset of the video sequence to locate motion. Motion can be detected by identifying lines that are not parallel to any of the vertices. Stationary subjects and lighting changes appear as lines parallel to one of the vertices. Thus, true motion can be distinguished from lighting changes.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application contains subject matter related to co-pending U.S. Patent Application Ser. No. 61/100,575, entitled “Video Analytics System, Computer Program and Associated Methodology for Efficiently Using SIMD Operations”, filed on Sep. 26, 2008, the entire contents of which being incorporated herein by reference. 
         [0002]    This application also claims the benefit of the earlier filing date of U.S. Provisional Application Ser. No. 61/100,579, entitled “System, computer program product and associated methodology for video motion detection using spatio-temporal slice processing”, filed on Sep. 26, 2008, the entire contents of which is incorporated herein by reference. 
     
    
     BACKGROUND 
       [0003]    1. Field of the Invention 
         [0004]    The present disclosure relates to video analytics, and, more specifically, a system, computer program product and methodology for detecting motion in videos using spatio-temporal slice processing to make the detection illumination-invariant. 
         [0005]    2. Description of the Related Art 
         [0006]    Video analytics extends beyond encoding and decoding video for desktop computer systems. Video analytics are techniques for analyzing content in still and video images, and are used to do more than determine a proper frame rate, resolution, and the like. In video analytics, image and video are analyzed for content, such as motion of items in an image(s). Often, uninteresting portions of a video are discarded, while other portions are analyzed in detail to extract relevant information, such as motion. 
         [0007]    Specifically, motion detection involves identifying spatial regions of images in a video sequence that are moving in an image space. This can include, for example, swaying trees and moving shadows, but not lighting changes or image noise. The problem of motion detection is made more complex by situations where a region of a video, stationary in all preceding frames, suddenly moves from one frame to the next. The inverse problem is also possible, i.e. a region in motion for many frames may stop abruptly. 
         [0008]    Many currently available motion detection methods and systems detect change rather than motion. These methods merely search for a difference in a region of an image between frames, or between a current frame and a series of preceding frames. For example, in the background subtraction method, a background or reference image is constructed from a set of previous frames in a video using, for example, an Infinite Impulse Response (IIR) filter. Then detection is performed by applying a threshold to the absolute difference between a current image and the background or reference image. The threshold may be a simple, binary function where the result is a “1” if the difference surpasses the threshold, and “0” otherwise. 
         [0009]    Other methods attempt to model the background using, for example, Gaussian distributions having a mean and a variance value. In the Gaussian Mixture Model, each pixel is represented by several Gaussian distributions, and each Gaussian distribution is weighted according to its variance and how many times it is observed. A pixel that does not fit within the background model unless its weight is reduced below a certain threshold is considered a foreground pixel likely to contain motion information. 
         [0010]    As recognized by the present inventor, methods that detect change and methods that attempt to model the background image are both very sensitive to changes in lighting. These methods simply cannot distinguish between “true” image changes and lighting effects while processing individual pixels. 
         [0011]    Moreover, also as recognized by the present inventor, motion estimation methods, which are usually based on comparing only two consecutive images, such as optical flow, which determine velocities for image regions in motion, are very computationally demanding, inaccurate or both. With more than two consecutive images being analyzed the computational demand is considered to be too high for practical application. 
         [0012]    Most currently available spatio-temporal filters analyze images individually and they use a high-level model to handle the temporal aspects, and the few spatio-temporal algorithms that simultaneously process a video spatially and temporally are too computationally demanding for real-time embedded processing. 
       SUMMARY OF THE INVENTION 
       [0013]    In view of the foregoing, an object of the present disclosure is to provide a system, computer program product, and associated methodology for video motion detection capable of correctly identifying motion in environments with heavy illumination changes, and doing so efficiently. 
         [0014]    An exemplary video motion detecting method combines a plurality of images of a video into an image volume. Each of the plurality of images includes a plurality of pixels, and the image volume has dimensions X corresponding to width, Y corresponding to height, and t corresponding to depth. After being formed the image volume is sliced along the (X,t) plane, and a logarithmic transform is optionally performed on each pixel to separate a reflectance components from an illumination component. 
         [0015]    A spatio-temporal filter is then applied to the sliced image volume, generating a filtered result. After filtering, the absolute value of the filtered result is put through a threshold function to generate a binary image that includes well defined spatio-temporal edges. Lastly, the binary image is searched for at least one connected string of pixels. A connected string of pixels that is not parallel to any of the axes indicates motion. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0016]    A more complete appreciation of the invention and many of the attendant advantages thereof will be readily obtained as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings, wherein: 
           [0017]      FIG. 1  is a block diagram of a network camera according to an embodiment of the present invention; 
           [0018]      FIG. 2  is a block diagram of a surveillance center computer, or a client computer according to an exemplary embodiment of the present disclosure; 
           [0019]      FIG. 3  is a block diagram of a surveillance system according to an embodiment of the present invention; 
           [0020]      FIG. 4  is an exemplary collection of images from a video sequence; 
           [0021]      FIG. 5  is an image volume that is sliced according to an exemplary embodiment of the present disclosure; 
           [0022]      FIG. 6  is a sliced image volume that has been filtered by a spatio-temporal filter according to an exemplary embodiment of the present disclosure; 
           [0023]      FIG. 7  is a sliced image volume to which a threshold has been applied after filtering according to an exemplary embodiment of the present disclosure; 
           [0024]      FIG. 8  is a rasterized series of search lines according to an exemplary embodiment of the present disclosure; 
           [0025]      FIG. 9  is a flowchart of a video motion detecting method according to an exemplary embodiment of the present disclosure; 
           [0026]      FIG. 10  is a flowchart of a search in the (X,t) direction according to an exemplary embodiment of the present disclosure; and 
           [0027]      FIG. 11  is a flowchart of a search in the (Y,t) direction according to an exemplary embodiment of the present disclosure. 
       
    
    
     DETAILED DESCRIPTION 
       [0028]    Referring now to the drawings, wherein like reference numerals designate identical or corresponding parts throughout the several views.  FIG. 1  is a block diagram of a network camera  10  (or an IP-camera) that may be used to capture images according to the present invention. More generally, however, the camera  10  may be any digital camera capable of generating image sequences and communicating the image sequences or image data from the image sequences, such as for example image meta data, over a network (private, public, or hybrid) to a user client ( 51 ,  FIG. 3 ). The term “video” in the present context is not limited to conventional motion pictures, but also includes still frames captured in time sequence (such as one per second, one per two seconds, etc.) The network camera  10  includes a local video analytics module  20 , shown in this embodiment as being implemented as a software based process on a processor  19 . However, a hardware, firmware, or hybrid module may be used as well. 
         [0029]    The network camera  10  includes a lens system  12  for collecting incident light, an image sensor  13 , e.g. a Charge Coupled Device (CCD), a CMOS-sensor or similar sensor, for registering incident light, an image processing module  15  (implemented in hardware, software, or hybrid approach), an image/video encoder  21 , a CPU  19  that manages, for example video analytics  20 , memory  17 , and a network interface  22 . The image sensor  13  could also be an IR-sensor for detecting infrared radiation. The image/video encoder  21  is arranged to encode captured digital image data into any one of a plurality of known formats for continuous video sequences, for limited video sequences, for still images or for streamed images/video. For instance, the image information may be encoded into MPEG1, MPEG2, MPEG4, H.264, JPEG, M-JPEG, bitmapped, etc. 
         [0030]    An analog camera ( 54 , shown in  FIG. 3 ), capable of generating analog image sequences, and a converter  57 , such as a video server or a video encoder, could also be used with, or as a substitute for, the network camera  10 . The converter transforms the analog image sequences from the analog camera  54  to digital image sequences or image data and providing the digital image sequences or image data to the network. In this case the video/image encoding and local analytics are performed in the converter. 
         [0031]      FIG. 2  is a schematic diagram of a client computer, or surveillance center computer according to the present embodiment. The computer  130  includes a computing device  100  to which a keyboard  112 , pointing device  111 , video acquisition unit  113  and a display  110  are connected. 
         [0032]    The computing device  100  includes a processor  101  that performs control processes and in connection with a main memory  105  for temporary storage of data being processed, and ROM  106  storing the instructions executed by the processor  101 . A disk controller  107  controls at least a disk  108  and a CD-ROM  109  where video sequences may be stored before and after processing. A display controller  104  is used to control an external display  110 , and an I/O interface is used to control other external devices, such as a keyboard  112 , a pointing device  111  and a video acquisition unit  113 . A bus  103  interconnects all of these components. 
         [0033]    The computing device  100  may be, for example, a PC employing a Pentium processor. The instruction set stored in ROM  106  may be provided as a utility application, background daemon or component of an operating system, or combination thereof executing in conjunction with a processor and operating system such as VISTA, UNIX, SOLARIS, LINUX, APPLE MAC-OS and other systems known to those skilled in the art. 
         [0034]    The main memory  105  of the computing device  100  may be dynamic or static random access memory (RAM) integral to the PC, or may be other memory devices such as FLASH, EEPROM, optical disk, servers, and the like. Additionally, at least part of the main memory  105  may also be detachable from the video motion detecting system. 
         [0035]    The video motion detecting system may also be implemented on hardware devices such as FPGA&#39;s, ASIC&#39;s, microcontrollers, PLD&#39;s or other such processing devices(processors). 
         [0036]    Examples of a video acquisition unit  113  include a video camera, a video cassette recorder (VCR), a Digital Versatile Disc (DVD) recorder, and the like. Examples of a pointing device  111  include a mouse, track ball, touch pad, etc., and a display  110  may for example be a video monitor. 
         [0037]    As shown in  FIG. 3 , a network camera  10  can either be locally connected via a private network or remotely connected via a public network to one or more user clients  51 . The network interface of the network camera enables communication between the camera and the user client of not only images or video but also control data of pan/tilt/zoom mechanisms, audio, image and video settings etc. The user client  51  could for example be a surveillance center  52 , a client computer  51  or a Network Video Recorder (NVR)  53 , may be a server for storing, manipulating and/or relaying image sequences from a camera).  FIG. 3  is intended to show different user clients that may interact with a monitoring camera. A network camera can serve more than one user client with for example images and video. 
         [0038]    Video analytics applications, such as motion detection, are based on analysis of images from the image sequences captured by the network camera  10  or the analog camera  54 . The analysis of the images may be performed in the network camera, in the surveillance center  52 , in the client computer  51  or in the NVR  53 . However, it may be advantageous to perform the video analytics in the network camera  10  or in the converter  57  because the video analytics may be performed without loading the network with traffic using a lot of bandwidth. Hence, this advantage is particularly relevant for applications in which the user is not interested in being continuously provided with image sequences, e.g. in applications where the user only is provided with image sequences if something happens in the camera view. With video analytics applications in the network camera  54  or converter  57  extraction of meta data, i.e. data about the images (like for example data describing what happens in the image sequence), is enabled. The transmission of image sequences from the camera to a user could then be substituted by meta data under certain conditions (for example when there are no alarms). Systems not sending image sequences continuously may be provided in order to save bandwidth or in order to facilitate scalability of the system, because it is easier to add further network cameras to such a system. An alternative embodiment, however, has the client computer  51  and/or the surveillance center  52  performing the video analytics. 
         [0039]    Next, a video motion detection method which may be executed on the video motion detection system of  FIG. 1  is described. 
         [0040]      FIG. 4  is a collection of images  201  of a video sequence  200  captured by, for example, the video acquisition unit  113  of the video motion detecting system. In this non-limiting example, the subject of the video sequence  200  includes a person  202 , a jacket  204  and a vertical column  203 . Of course, as can be appreciated by one of ordinary skill in the art, the method may also process images containing other subject matter. Further, the images  201  may be arranged with the most recent image in front of the others, or with the most recent image behind all of the others. 
         [0041]    In  FIGS. 4 and 5 , the images  201  of video sequence  200  are combined to form an image volume  300 . The video sequence  200  comprise images  201  I 1 , I 2 , . . . I N , where Nis equal to or greater than 3. Then the image volume  300  is sliced along the (X,t) plane to form two image volume portions  301  and  302 . However, the image volume  300  may also be sliced along the (Y,t) plane without departing from the scope of the present disclosure. 
         [0042]    The top of the image volume  301  includes the column  305 , the person  303  and at least one dark, horizontal line  304  (parallel to the Y axis). The column  305  is stationary, and thus forms a line parallel to the t axis (i.e. the time axis). However, the person  303  has moved during acquisition of the video sequence  200 . As a result, the person  303  forms a curve along the top of the image volume portion  301  that is not parallel to any axis. 
         [0043]    The dark horizontal lines  304  represent lighting changes. For example, line  304  is the result of diminished lighting. However, as recognized by the present inventor, such lighting changes are always parallel to the X or Y axis, and can therefore be readily identified as a lighting change, not motion, and suppressed. Such suppression of lighting changes is not possible with difference detection or motion estimation methods. 
         [0044]    After the image volume  300  is sliced into image volume portions  301  and  302 , a logarithmic transformation is applied to each pixel in the two image volume portions  301  and  302  to separate a reflectance component and an illumination component. Optionally, the illumination component may be suppressed by high-pass filtering the pixels in the image volume  300 . 
         [0045]    Next, the image volume  300  is filtered with a spatio-temporal filter to yield the image volume  400  of  FIG. 6 . The spatio-temporal filter is an edge enhancing filter. As such, the spatio-temporal filter enhances the edges of the person  403 , and the column  404 . 
         [0046]    For example, Spatio-temporal filtering may be accomplished using a 3×3 Sobel filter kernel. Further, spatio-temporal filtering may also be accomplished using the method described in Application Serial No.  61 / 100 , 575 , which employs Single Instruction Multiple Data (SIMD) instructions to simultaneously process multiple pixels while holding a number of bits per pixel constant throughout filtering. 
         [0047]    After filtering with the spatio-temporal filter, or together as part of the filter, a threshold function is applied to the pixels of image volume  400  for data reduction.  FIG. 7  is the resulting image volume  500 . The threshold functions further accentuates edges through a binary representation of each pixel. For example, pixels that meet a predetermined threshold value (e.g. ≧50% gray value) are given a value of “1” (black) and pixels that fall below the threshold are given a value of “0” (white). In image volume  500 , the edges that define the person  503  are clearly distinct from their surroundings, as are the edges that define the column  504 . This allows for more efficient searching of the image, as described below since each pixel is now represented by only a “1” or a “0”. 
         [0048]      FIG. 8  is an image portion  600 , in the (X, t) plane, that has been processed as described above. Pixel  601  is identified in this example as the starting pixel. From pixel  601  rasterized search lines  602   a ,  602   b ,  603   a ,  603   b ,  604   a  and  604   b  extend to the edge of the image portion  600 . Searching involves identifying strings of pixels along the search lines that all have a value of “1” (i.e. that are all black.) The string of pixels must be of a predetermined length (such as a number of linearly arranged pixels across an image being searched, or a specific number, such as 3, 5, 8 (shown), or 10 pixels) for the method to identify it as representing motion. For example, a string may be required to be as long as the image portion  600  being searched, which is a maximum of 8 pixels in the example. However, shorter or longer detection string sizes may be used as well in the present embodiment. Further, a single break in the string may be sufficient for the string to be disregarded as an artifact, noise, etc. 
         [0049]    The size of the image portion  600  being searched determines the accuracy and noise-susceptibility of motion identification. If the area is small, (such as 3, or 2 pixels in a direction) the likelihood is greater of obtaining more positive detection results, but those detection results are more susceptible to corruption by noise than longer detection strings. Larger (e.g. areas having between 8, 9 or 10 pixels in a direction) image portions  600  are more immune to noise disturbance, but result in fewer detection results. However, any positive detection result for a longer contiguous string provides more reliable detection information than a shorter string. 
         [0050]    Additionally, angles corresponding to the search lines ( 602   a ,  602   b ,  603   a ,  603   b ,  604   a  and  604   b ) may be varied over a range (e.g. 30° to 60°) to detect motion of differing velocities. 
         [0051]      FIG. 9  is a flowchart of the above-described process. In step S 1 , the plurality of images  201  of video sequence  200  are combined onto an image volume  300 . The image volume  300  is sliced along one of the (X,t) plane or the (Y,t) plane in step S 2 . The image volume  300  is subjected to a logarithmic transformation at step S 3 , and filtered by the spatio-temporal filter at step S 4  to generate a filtered image volume  400 . The threshold function is applied to the filtered image volume  400  at step S 5  and detection of motion (in either (X,t) or (Y,t)) is carried out in step S 6 . By changing the direction of slicing from (X,t) to (Y,t) and vice versa a complete motion detection analysis is performed on the video sequence. 
         [0052]      FIG. 10  is a flowchart of the detection performed in step S 6  of  FIG. 9  in the case of slice processing along an (X,t) plane. At S 10  a pixel having a value of “1” is selected as a starting point. The adjacent pixel at location (X+i, t+j) is probed to determine whether its value is a “1” or a “0” at step S 11 . If its value is a “ 1 ” this pixel is selected as the new starting point at step S 12 , and a counter that keeps track of the number of adjacent pixels identified with a value of “1” is incremented at step S 13 . Then steps S 11 -S 13  are repeated until the entire search line is searched. 
         [0053]    The index variables i and j may be incremented by 1 or 2 in order to implement the search lines of  FIG. 8 . For example, search line  602   b  is generated when the increment for i is 2 and the increment for j is 1. The search line  603   b  is generated when the increment for both i and j is 1, etc. Other values for i and j are possible, however, to implement search lines with different angles. 
         [0054]    Once a search line is fully searched, the number adjacent pixels having a value of “1” is compared to a threshold at S 14 , and if this number surpasses the threshold, motion is detected at S 15 . However, if this value falls below the threshold, no motion is detected (step S 16 ). The search repeats for every search line until all are exhausted, and then execution is returned to the main loop. 
         [0055]      FIG. 11  is a flowchart of the search process in the (Y,t) direction. As in the above-described case, a pixel with a value of one is selected as a starting point at S 20 . The next adjacent pixel (Y+i, t+j) is probed to determine whether its value is a “1” or a “0” at step S 21 . A “1” will cause pixel (Y+i, t+j) to be selected as the next starting point at S 22 , and a pixel counter to increment at step S 23 . Once a search line in exhausted the value of the pixel counter is compared to a threshold at S 24 . A detection occurs at S 25  when the value is higher that the threshold. Otherwise no motion is detected (S 26 ). Steps S 21 -S 23  repeat until the search line is exhausted. 
         [0056]    As in the case of the (X,t) search, the values of i and j can be 1 or 2 to implement the search lines of  FIG. 8 . However, other values are possible. Once all search lines are exhausted, control reverts to the main loop. 
         [0057]    The above-described search can be performed in concentric circles of expanding image areas to increase the likelihood of detection without appreciably reducing accuracy. Presume there is a two-dimensional detection area, defined by axes X and Y. In the search area, a number of short and long detection strings will be present. As a method for efficiently detecting edges, the longer detection strings may be used as “seeds” to be used for focusing-on areas to be analyzed. Moreover, once a longer string is detected, that longer string is a significant finding that an edge is present with high probability. Then, anchored in a search region by the long detection string, circular areas around the long detection string may be searched for lower confidence samples. The reasoning behind this search strategy is that the longer detection strings have a high probability of being accurate, and therefore are more likely to be indicative of an actual edge. Since an edge has been detected with high confidence in this area, it is reasonable to presume that other parts of the edge will be located in a nearby area. It follows that short detection strings located in more remote, isolated portions of the detection area, are more likely to be the product of noise, and therefore not as likely to be caused by an actual edge. 
         [0058]    In one embodiment, the present inventor recognized an advantage of representing each pixel by one bit. Namely continuous lines throughout the detection range are detected by logical AND operations of adjacent rows in the detection area. For example, contiguous string  603   b  may be detected by a series of AND operations on different data rows (in the t direction). Thus, through straight-forward Boolean logic, contiguous detection strings are readily identifiable though a series of AND operations. Likewise, once the detection strings are formed in the area  600 , the presence of any single string of sufficient length (in this case, a contiguous string from pixel  601  to the edge of the area  600 ) is identifiable by a logical OR for each candidate string. Therefore, if any one string is present, the result of the OR operation indicates that a string of sufficient length is present in the area  600 , and consequently, an edge is present and includes pixel  601 . 
         [0059]    While the present embodiment describes representing one bit per pixel, it is also possible to include multiple pixels per word, such as 32 pixels per word. In this case, parallel searching is performed for diagonal strings originating from pixel  601  and the 31 pixels to its right, for example, along the x-axis. In this case, parallel searches are performed in parallel diagonal directions. It is noted that multiple bits per pixel requires more complicated arithmetic iperations, thus increasing the processing demand. 
         [0060]    While  FIG. 8  shows strings in a straight line, it is also possible to have other patterns of lines detecting motion, not necessarily linear. Such other patterns include partially diagonal lines, which includes one or more diagonal segments, and curved lines. 
         [0061]    In another embodiment the search procedure is performed for all pixels in the (X,Y) plane simultaneously in parallel. Starting with the latest edge image in the image volume  500 , a logical AND is performed with the next image which has been translated according to the search line and then logically compared, using the AND-operation, to the result of the first AND-operation. This procedure is then repeated to cover a predetermined length of pixels. The search procedure is repeated for different search lines having different directions. Logical OR-operations are used between the different search directions to determine if there is motion detected in any one of the search lines originating from a specific starting pixel. This search procedure may be performed for both translations in the X-direction and in the Y-direction. Using this search procedure an explicit slice step S 2  is not necessary in process shown in  FIG. 9 , since the slicing will be inherent to the detection step S 6 . 
         [0062]    The above described method may also be implemented as computer-readable instructions stored on a computer readable medium. 
         [0063]    Conventional video motion detection methods are computationally demanding, inaccurate or sensitive to changes in lighting. However, a video sequence may be combined into an image volume, and sliced along an (X,t) or (Y,t) plane. As the present invention recognized, motion on such a slice appears as a slanted line or curve that is not parallel with any axis (X,Y,t), while lighting changes and stationary objects appear as lines parallel to one of the axes. Therefore, in this method, lighting changes can be identified and suppressed or discounted. 
         [0064]    Further, as recognized by the present inventor, searching along search lines, rasterized to the video sequence, allows for improved efficiency over current methods, and lends itself to implementation in embedded systems. 
         [0065]    Obviously, numerous modifications and variations of the present invention are possible in light of the above teachings. It is therefore to be understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described herein.