Motion detection in a video stream
Contents
1. fn p q Test NO YES Proceed for VMD PAA OS Patent Application Publication Nov 2 2006 Sheet 1 of 9 US 2006 0245618 Al Fig 1 Set pix_count Set Bg flag 0 Store first image after neighborhood averaging as Bg image and old image fn 5 Ntergneiehborhoodfavenzeines f s fes DAG img Fiel Sum Ae Ea BES Column q location in a sequential array and check the previous condition only for these Diff img p g lt k1 Sum_img p q d l Increment pi count NO Ifpix count image size Set Bg flag 1 Proceed for VMD Maso hito Una eee ak Patent Application Publication Nov 2 2006 Sheet 2 of 9 US 2006 0245618 Al Fig 2 SEE AA Find Div img fal Gat Being CAN i DN p prs Find n mean in Div img g taking only pixels which are in the range of 0 4 amp 0 6 Set Low threshold k2 mean Div img Div img p q lt Low threshold OR Div_img p q gt High threshold Bin _img p q o EISEN TIEREN RE gt a TREE Bin img pq 255 gees ebene BRP ERA ee his re Patent Application Publication Nov 2 2006 Sheet 3 of 9 US 2006 0245618 Al Find squared pixel difference along vertical direction _ Kai beach ANETTE t N PE RET Find squared pixel difference along horizontal direction Find Squre rooteof the abOVESUMIONgEN2. Binary Edge segmentation map is obtained using the fixed threshold as given below Binary Edge Confidence Map BE 1 Az hr BE y als J 0 Otherwise Morphological operators are then applied on the edge map The overall flow of the Edge model is shown in the flowchart of FIG 7 Color Luminance Model 0058 For Luminance Y channel background model is build using the weighted sum of mean and the current pixel value NY BY 0t vs Ya X y 1706 s Ha 15 22 A difference mean image is computed which is used to threshold and segment the image as foreground or back ground NO Yay Sy Hay Q3 Binary Color Confidence Map BC 1 ACz1 asg Foreground BCwy Xs y 0 Otherwise Background 0059 The color luminance model evaluation process is further summarized in the flowchart of FIG 8 Contrast Model 0060 The images are initially subjected to a pre process ing step wherein RGB to Gray intensity or luminance conversion is carried out and this image is passed through an averaging 3x3 neighborhood averaging filter The aver aging filter smooth en the image and helps in reducing the effect of noise 0061 If the gray level value at a given pixel location is La at time t and f st y at time t 5 five frames earlier the sum and difference images are obtained as follows Nov 2 2006 Difference image Diff Image abs f 0 f sl 24 Sum image Sum Image f te sy 25 Threshold Image K1 Sum Image
3. Unwanted tree motion caused due to low and moderate breeze winds will be slowly learnt However any motion blobs that are created due to such motion would be filtered due to the application of the MOS criteria or would be eliminated in the tracker due to the inconsistency US 2006 0245618 Al of the track association Shadows with low brightness and the shadows that are thin are NOT detected as motion regions due to the dependence of the global BGND thresh old on the average variance of the frame Conclusion 0091 The examples presented here illustrate by way of example algorithms and embodiments how video motion detection can be improved to provide better detection of moving objects and better discrimination between a moving object and other environmental occurrences such as shad ows weather or a slowly changing background Extracting color information to estimate regions of motion in two or more sequential video frames and extracting edge informa tion to estimate object shape of the moving object in two or more sequential video frames enables combining the color information and edge information to estimate motion of the object more robustly than was possible with previous tech nologies 0092 Although specific embodiments have been illus trated and described herein it will be appreciated by those of ordinary skill in the art that any arrangement which is calculated to achieve the same purpose may be substituted for the sp
4. Edge Mean Update Han X Y 0 gage S Hen Co Y 1 G age suia Co Y Hs Yn GG Y 0 gage rte Lt Y 0 pago sy qu BI Mean Update Al lusu Go y SHm y A Just x y Srn Go Y Delta Gradient A12 A1 A2 A A1 A2 A12 Patent Application Publication Nov 2 2006 Sheet 8 of 9 US 2006 0245618 Al Fig 8 Y 0 299R 0 587G 0 114B Adaptive threshold Q avg a r c S Y Xj baten 53 Gn x 0 y 0 x 0 y 0 o Ane Ya 2 Color Mean Update Kn x y Dave Yay Y a zi Doug Jut yr y AC roy G3 Metz y Generate Binary Color Segmentation Map BC 1 Cale BC ny y T 30 MO Patent Application Publication Nov 2 2006 Sheet 9 of 9 US 2006 0245618 Al Fig 9 Y 0 299R 0 587G 0 114B Y SmoothImageFilter SEF 7 Background Learning Edge Strength ED Calculation l 2 2 AED G5y A 05 Bletz LA Glo 95 SI Gy DY SIBG y GG y ST n3 X3 y SIBGs s quy Go y BG 29 01 SI Gs y 1 21 BG G9 AER os BRED BA L HBG 59 BG Gs 7 SI bigin 39 80 005 SI sumen x y ST sumin C5 Y Sle kX y Sla BY k const Le AED Thr 9 3 AEDI kl re kl constant x 0 y 0 M AED 2Thr 9 3 AED 2 k2 rc Ki constant iz0 j 0 Generate Binary Color Confidence Map BC1 SIBG s quy y Soy BG q Y 1 SIE Tel SIB Gc y eHThr Binary Edge Segmentation Map BE1 BAY o otherwise _ 1 AEDIEIEDIThr amp amp AED2SAE
5. Edge Strength Current Image and Edge Strength Div Image d the mean en m both Current image and Division image to fix different threshold for sach mae Check Edge Strength Current Image p q gt Thresholdl amp amp Edge Strength Div Image p q gt Threshold2 No Patent Application Publication Nov 2 2006 Sheet 4 of 9 US 2006 0245618 Al Figure 4 Check Edge Strength Bin Image p q Binary Image p q 510 amp amp Start flag No SA San Nag cT TAE Se ish ee ENTE Chec Bin Image p q 255 amp amp Start_flag 0 Bin Bin_Image p q Edge Strength Bin Image p q 0 amp amp Start flag 1 Set Start flag 0 E AE AE Patent Application Publication Nov 2 2006 Sheet 5 of 9 US 2006 0245618 Al Figure 5 EE Patent Application Publication Nov 2 2006 Sheet 6 of 9 US 2006 0245618 Al Fig 6 Edge Model No of Object gt 0 Color Model Contrast amp Edge Strength Model Refine Motion Segmented Output Binary BC amp BC1 Based on of Objects in Color and Edge Model Post Processing Median Filter Region Labeling Hole Filling Final Binary Map B BC BC1 BE BEI Patent Application Publication Nov 2 2006 Sheet 7 of 9 US 2006 0245618 Al Fig 7 Y 0 299R 0 587G 0 114E Y EdgeFilter EF X X SobelFilte r SEF gt S
6. Height in this case will be approximately 81 pixels Similarly the MOS for Human Width for the same Human sample object turns out to be approximately 31 pixels Application of these values indi vidually to the object height and width would enable better filtering It is to be noted here that actual MOS Height and MOS Width could be a percentage approximately 7096 of the theoretical value for best results Note this calculation does not give the actual MOS actual pixels on the object body but it gives the pixel values corresponding to the MBR enclosing the object Hence a percentage of these values could actually be considered for application rather than the computed values which are too large Guidelines on Setting Correct Camera Field of View and Marking Region of Interest 0087 The camera FOV setup and ROI selection should be done with care for best performance and results The camera is desirably located mounted in such a manner as to satisfy the following criteria with respect to the FOV and hence the ROI 1 FOV should be centered w r t the video frame as far as possible 2 FOV should include majority of the location or extent of the scene to be monitored 3 FOV should be focused correctly by adjusting the camera focal length for best viewing 4 FOV should include the farthest nearest locations to be monitored in the scene 5 Object skew due to camera orientation should be avoided within the FOV 6 Place the cam
7. between moving objects and background regions and user specified parameters such as minimum object size regions of interest in the video frame and other such parameters Separation Between Moving Objects 0075 The moving objects need to be reasonably sepa rated in the field of view FOV or the ROI for best perfor mance This factor is very critical here since the image or video frame available to us only provides a 2D perspective view of the objects can be overcome provided the camera resolution allows the estimation of shade depth and hence the 3D information of objects which is beyond the scope of this algorithm Further the object position estimation pre diction performed by further modules that could be depend ing on the above algorithm such as the object tracker works best with a minimum separation of 3 pixels between the object contours or boundaries to differentiate objects as separate or else would result in merging of tracks Such merged objects could get classified wrongly in further analy sis owing to the indefinite shape and size as many shape features used on the OC algorithm could result in relatively wrong values Speed of Moving Objects 0076 The average speed of moving objects is desirably reasonably high and consistent for successful video motion detection Problems that occur due to speed of object most visibly impact both indoor and outdoor scenarios Any object moving at very low speed usually near f
8. region of interest in the video data stream 7 A video monitoring system comprising a video signal interface operable to receive a video signal from a camera a video processing module operable to analyze the received video signal the analysis comprising Nov 2 2006 extracting color information to estimate regions of motion in two or more sequential video frames extracting edge information to estimate object shape of the moving object in two or more sequential video frames and combining the color information and edge information to estimate motion of the object 8 The video monitoring system of claim 7 the received video signal analysis further comprising extracting contrast information from two or more sequential video frames and combining the extracted contrast information with the color information and edge information in estimating motion of the object 9 The video monitoring system of claim 7 wherein combining the color information and edge information com prises correlating the information to estimate the position and motion of the object 10 The video monitoring system of claim 7 the received video signal analysis further comprising using the color information and edge information to update a learned back ground image record 11 The video monitoring system of claim 7 wherein the video stream comprises video frames at a frame rate between and including five to twenty frames per second 12 The video mo
9. takes a certain amount of time to learn the exposed background area where object was residing earlier This problem can be avoided if we somehow combine the current edge image with the binary image output of motion detection routine This is done by first extracting the edge strength image which is common to both division image and the current image The actual procedure involves finding the row difference and column difference image and combining both as explained below Find gray image rowdiff p g gray image ro pr1 q gray image ro p q for all the rows over the entire image Find gray image coldiff p g gray image col p q l gray image col p q for all the columns over the entire image Find Edge Strength Current Image p q Sqrt gray image rowdiff p q 2 gray image coldiff p q 2 Where p q are the row and the column indices of a given pixel in the image under consideration Nov 2 2006 0032 Similarly Edge Strength Div Image is also obtained for division image After this step mean grey level of Edge Strength Current Image and Edge Strength Di v Image are separately determined to compute separate thresholds for both the edge strength images Let us call Thrl and Thr2 as thresholds for Edge Strength Current I mage and Edge Strength Div Image respectively Using these two thresholds simultaneously a single Binary Edge Image is obtained using the following logic If Edge Strength Current Image p q gt Thri
10. 26 Where Constant k1 Multiplying factor which decides the gray level variation between the two video frames that can be allowed to qualify a given pixel as a background pixel or not It is chosen in the range of 0 0001 to 0 001 0062 The value of each and every pixel in the Diff Im age is compared with a corresponding pixel in the Thresh old Image and if a given pixel is less than the Thresh old Image value it is considered as static background pixel If Diff Image x y lt Threshold Image x y Bgnd Image x y f x y 27a Where Bgnd_Image x y is the learnt background image pixel x indicates columns amp y indicates rows 0063 The location x y of all the pixels which do not satisfy the above condition is stored in a sequential array In the next frame only those pixels that are available in the sequential array are tested for the above If condition and the process is repeated in every frame till the number of learnt background pixels is same as the image size 0064 To avoid the appearance of artifacts occurring due to illumination changes during the process of learning after the above mentioned threshold comparison step 17a the following steps are carried out in every frame using the above Diff Image Sum Image Threshold Image and Bgn d Image If Diff Image x y Threshold Image x y Bgnd Image x y a Bgnd Image x y 1 a x y 27b The value of a i
11. Background Learning Mechanism 0021 The background learning used in the example video motion detection algorithm works as follows When we monitor a given scene over a period of time any object which is moving would normally result in considerable change in gray level at those pixel locations whereas in the areas where there is no activity or motion gray level value of the pixels remains almost same To monitor this change in gray levels we have considered difference image and sum image that are obtained using the current image and old image 5 frames old and the difference image is thresh olded using a scaled version of sum image This method of thresholding has been found to be robust to change in illumination levels of the scene Those pixels in the differ ence image that are below the threshold are considered as background pixels and hence the pixels in the corresponding locations of the current image are learnt as background Nov 2 2006 pixels In the next video frame the pixels which are not learnt earlier are only considered and the process is repeated over a number of frames until the entire image is learnt as background Once the background is fully learnt the algo rithm declares that the background is learnt and it switches to a video motion detection VMD routine 0022 If the gray level value at a given pixel location is fn p q at time t and fn 5 p q at time t 5 five frames earlier the sum and difference image
12. D2 Thr BEL atz 3 0 Otherwise US 2006 0245618 Al MOTION DETECTION IN A VIDEO STREAM CROSS REFERENCE TO RELATED APPLICATIONS 0001 This application claims priority to India Patent Application No 1061 DEL 2005 filed Apr 29 2005 which is incorporated herein by reference FIELD OF THE INVENTION 0002 The invention relates generally to analyzing video data and more specifically to motion detection using back ground image processing for video data BACKGROUND 0003 Video cameras are commonly employed in security and monitoring systems providing a user the ability to monitor a wide variety of locations or locations that are physically remote from the user The video cameras are often also coupled to a video recorder that records periodic images from the video camera or that records video upon detection of motion Such systems enable a user to monitor a location in real time but also enable a user to review events that occurred at a monitored location after an event such as after a burglary or to confirm some other event 0004 Monitoring a large number of cameras requires a large number of monitors and a number of guards sufficient to keep an eye on each monitor Simply employing more monitors and more guards in large facilities such as manu facturing plants military bases and other large environ ments is not a desirable solution because of the additional cost involved and so automated solutions to monitoring
13. US 20060245618 A1 a2 Patent Application Publication 10 Pub No US 2006 0245618 A1 as United States Boregowda et al 54 MOTION DETECTION IN A VIDEO STREAM 75 Inventors Lokesh R Boregowda Bangalore IN Mohamed M Ibrahim Kayalpatnam IN Mayur D Jain Akola IN Venkatagiri S Rao Bangalore IN Correspondence Address HONEYWELL INTERNATIONAL INC 101 COLUMBIA ROAD PO BOX 2245 MORRISTOWN NJ 07962 2245 US 73 Assignee Honeywell International Inc 21 Appl No 11 223 177 22 Filed Sep 9 2005 Set pix_count Set Bg flag 0 Store first image after neighborhood averaging as Bg image and old image fn 5 43 Pub Date Nov 2 2006 30 Foreign Application Priority Data Apr 29 2005 IN 1061 DEL 2005 Publication Classification 51 Int CI GO6K 9 00 2006 01 BE US o UMOR ee 382 107 57 ABSTRACT A moving object is detected in a video data stream by extracting color information to estimate regions of motion in two or more sequential video frames extracting edge infor mation to estimate object shape of the moving object in two or more sequential video frames and combining the color information and edge information to estimate motion of the object sequential array and check the previous condition only for these Lane i Diff img p q lt k1 Sum img p q If pix count image size Set Bg flag 1 Bg img p q
14. a number of video signals for events have been explored 0005 One technology commonly used to automatically monitor video signals for activity is use of a motion detec tion algorithm to detect when one or more objects in the video signal are moving relative to a background Such systems can be used to monitor for intrusion or unauthorized activity in the field of a variety of video cameras and alert a user upon detection of motion in the video stream For example such a system may monitor twenty video streams for motion and upon detection of motion in one ofthe video streams will sound an alarm and display the video signal with detected motion on a video display 0006 The reliability and accuracy of video motion detec tion is therefore important to ensure that such systems provide adequate security and can be relied upon to monitor video signals for unauthorized activity in place of human security personnel False detections of motion should there fore be kept to a minimum to ensure that detected motion events justify attention and intervention of security person nel Further the detection probability should be as high as possible to ensure that unauthorized motion events do not go undetected The motion detection system should further be insensitive to environmental variations such as snow rain and cloudy weather and should work in a variety of lighting conditions Accurate motion detection is also impor tant in systems in whic
15. amp amp Edge Strength Div Image p q gt Thr2 Binary Edge Image p q 255 Else Binary Edge Image p q 0 Where p q are the row and the column indices of a given pixel in the image under consideration The flowchart of FIG 3 illustrates this method of generation of an edge strength image Combining Edge Strength Binary Image with the Motion Detected Binary Image 0033 To eliminate spurious pixels in VMD output the correspondence between the edge strength image and the VMD output binary blobs is established using three If Else loops as explained below For this the VMD binary image and the edge strength image are scanned from left to right along top to bottom direction row by row Initially a flag known as Start flag is set to zero and the VMD output is copied into two arrays known as Bin imgl and Bin img2 Start flag 0 Bin imgl Bin img Bin img2 Bin img If Bin_imgl i j Edge img ij 510 amp Start flag 0 Start flag 1 Else End If Start flag 0 amp Bin imgl ij 255 Bin imgl ij 0 Else End If Start flag 1 amp Bin imgl ij Edge img ijj 0 Start flag 0 Else End Start flag is set to zero at the beginning of each and every row before applying the If Else condition i j are the row and column indices of a given pixel in the images under consideration Similarly Bin img is modified by traversing in the right to left direction Afterwards fina
16. based on the above criteria On the other hand user defined regular irregular ROI s are a very effective means of deriving the best performance of the algorithms by avoiding regions in the FOV that could result in object occlusion object split object merge with BGND dark corners thick shadows etc Also care should be exercised while installing and config uring cameras at busy locations such as shopping malls airport lobbies indoor parking lots airport car rentals pick up locations etc Experimental Results 0089 The example algorithm presented above is highly robust in rejecting false motion created due to various extraneous events such as those listed below Unwanted motion created due to moving shadows of clouds across the region under surveillance is ignored the effects of such variations are learnt very fast by the algorithm approxi mately within 10 to 15 frames or within 2 to 3 seconds ofthe advent ofthe cloud shadow In any case these initial motion blobs would be ignored or rendered redundant by the tracker 0090 All moving objects which pass below existing broad frame spanning shadows cast due to large stationary bodies in the scene such as buildings tall trees are reliably detected since such shadows are well learnt by the algo rithm Unwanted Pseudo motion created due to falling snow rain is completely rejected by instantaneous learning of BGND due to the continuously adaptive learning param eter ALPIIA
17. ecific embodiments shown This application is intended to cover any adaptations or variations of the example embodiments of the invention described herein It is intended that this invention be limited only by the claims and the full scope of equivalents thereof 1 A method to detect a moving object in a video data stream comprising extracting color information to estimate regions of motion in two or more sequential video frames extracting edge information to estimate object shape of the moving object in two or more sequential video frames and combining the color information and edge information to estimate motion of the object 2 The method of claim 1 further comprising extracting contrast information from two or more sequential video frames and combining the extracted contrast information with the color information and edge information in estimat ing motion of the object 3 The method of claim 1 wherein combining the color information and edge information comprises correlating the information to estimate the position and motion of the object 4 The method of claim 1 further comprising updating a learned background image record using the color informa tion and edge information 5 The method of claim 1 wherein the video stream comprises video frames at a frame rate between and includ ing five to twenty frames per second 6 The method of claim 1 wherein information is extracted to estimate motion in only a selected
18. eld and near field scenarios add further dimensions of variation to the existence and defini tion of the object in the motion map binary representation of the FGND and BGND There exist further complications that could arise due to the visible fact that a vehicle such as a car moving at far field location could result in the same binary map as a human at near field location Also a smaller MOS could be sufficient for allowing the establishment of a track while the same MOS would prove insufficient for any classifier to properly estimate the shape information MOS also doubles up as a very useful factor to filter out false motion due to snow rain etc Owing to all these facts and in view of the enormity of the impact of MOS it is strongly suggested to approach the problem from the optical perspec tive to decide the most appropriate MOS The MOS in the current version has been fixed separately for outdoor and indoor scenarios But it is to be noted that depending on the nature of mounting the camera both outdoor and indoor scenes could have far field and near field cases in many situations Hence it would be most appropriate to derive the MOS based on the following parameters available to us 0078 1 Camera CCD resolution obtained from the camera user manual 0079 2 Camera focal length obtained from the camera user manual 0080 3 Frame Capture Resolution CIF QCIF 4CIF etc 0081 4 Vertical distance height of camera placem
19. ent 0082 5 Horizontal distance of the farthest point in the FOV under surveillance Refer to Notes at the end of this section 0083 6 Assumed typical height and width of humans and vehicles 0084 Using the above factors the MOS Height and MOS Width can be computed separately as shown in the sample computation below sample MOS Height for a typi cal Human object for an outdoor scenario Sample Minimum Object Size Calculation for Human Height MOS 0085 SSC DC393 V5 type Interline Transfer Exwave HAD CCD 768 x 494 13 format 4 8 x 3 6 mm NTSC standard 480 TV lines 8 mm f Camera type Image device Picture elements H x V Sensing area Signal system Horizontal resolution Focal Length US 2006 0245618 Al Total field of view FOV can be calculated using the relation 2 tan d 2f z 1 Vertical FOV 2 tan 3 6 2x8 i e Vertical FOV 25 36 degress Or in other words Vertical FOV 25 degrees and 21 min utes 36 seconds No of Vertical Pixels on CCD 494 _FOV vertical 25 36 494 _FOV 0 05134 degrees Let the object s vertical size is say 6 feet for Human X Camera to Object Range R Sqrt horizontal dis ancey Vertical distance Angle subtended by the object at camera theta X Rx180 Pi degrees 6 82 5 x 180 3 14 X Therefore 024 169 No of pixels occupied by the object along the vertical axis is sl FOV 4 16 0 05134 81 pixels 0086 Hence the MOS for Human
20. era as high as possible in Indoor locations for good FOV 7 Place the camera as low as permissible in Outdoor locations for good FOV 8 Avoid camera placement at corners under roofs in Indoor locations for good FOV 9 FOV should avoid containing thick poles or pillars to avoid split objects Nov 2 2006 10 FOV should contain as less static moving objects such as Trees Small Plants 11 FOV should exclude places which could contribute to intermittent object stoppages 12 FOV should avoid very thick shadows to help clear object exposure to the camera 13 FOV should try to avoid reflecting surfaces to the extent possible 14 Avoid placement of camera in narrow passages rather place camera at exit entrance 15 FOV should avoid elevator doors stairs escalators phone booths wherever possible 16 Avoid placement of camera opposite to reflecting sur faces and bright corners 17 As far as possible avoid placing the outdoor camera towards East and West directions 18 FOV should avoid regions of continuous motion such as rivers etc except far field 19 FOV should avoid freeways motorways expressways unless deliberately required 20 Only far field FOV s should be allowed to contain corners of roads walkways 0088 The ROI drawn by the user has a complete rel evance to the FOV and could either supplement or comple ment the FOV as per the scenario under consideration Hence ROPs too should be drawn or selected
21. fference images and combining both as detailed below Compute the Row and Column difference images respectively as Gray Image Coldiff x y f x 1 YI AG y 29 Gray Image Rowdiff x y 2f x y 1 f x y 30 Nov 2 2006 continued Else Binary Edge Image x y 0 Where x y are the row and the column indices of a given pixel in the image under consideration Combining Edge Strength Model Information with Contrast Model Information 0069 To eliminate spurious pixels in video motion detec tion output the correspondence between the Edge Strength Bin Image and the video motion detection output binary blobs is established in one example embodiment by using three if else loops as explained below For this operation the video motion detection binary image and Edge Image are scanned from left to right along top to bottom direction row by row Initially a flag known as Start Flag is set to zero and the video motion detection output is copied into two arrays known as Bin Image and Bin Image2 Start Flag 0 Bin Imagel Bin Image Bin Image2 Bin Image Then compute the edge strength image as Edge Strength Current Image x y Sqrt Gray Im age Coldiff x y 24 Gray Image Rowdiff x y 2 31 Where x y are the column and row indices of a given pixel in the image under consideration 0068 Similarly Edge Strength Div Image is also obtained for division image After this step mean grey level of Ed
22. five to twenty frames per second 18 The machine readable medium of claim 13 wherein information is extracted to estimate motion in only a selected region of interest in the video data stream
23. g object in two or more sequential video frames and combining the color information and edge information to estimate motion ofthe object 0018 Detection of moving objects is an important part of video camera based surveillance applications Many examples of video motion detection algorithms employ US 2006 0245618 Al background subtraction to detect any activity or motion in the scene Therefore it is desirable to first learn the static background scene that does not contain any moving fore ground objects If there are foreground objects that are moving continuously in the scene then it becomes a prob lem to identify and learn the static background scene Various embodiments of the present invention address this problem such that the learnt background can be used to implement subsequent motion detection algorithms In fact the same method can be applied to continuously update the background once the initial learning phase is completed 0019 In one example instead of using conventional image subtraction approach for motion detection the current image is divided by the sum of current image and learnt background image to generate a division image The divi sion image is subjected to a threshold operation to get the motion detected image Further robustness is achieved by combining the motion detected image with the edge strength image The method is described below 0020 In the first step the color image obtained from the ca
24. ge Strength Current Image and Edge Strength Di v Image are separately determined to compute separate thresholds for both the edge strength images Let us call Threshold1 Threshold2 as thresholds for Edge Strength Current Image and Edge Strength Di v Image respectively Using these two thresholds simulta neously a single Binary Edge Image is obtained using the following logic and If Edge Strength Current Image x y gt Threshold amp amp Edge Strength Div Image x y gt Threshold2 Binary Edge Image x y 255 If Bin Imagel x y Edge Image x y 510 amp Start Flag 0 Start Flag 1 Else End If Start Flag 0 amp Bin Imagel x y 255 Bin Image 1 x y 20 Else End If Start Flag 1 amp Bin Image 1 x y Edge Images y 0 Start Flag 0 Else End 0070 Start Flag is set to zero at the beginning of each and every row before applying the if else condition Similarly Bin Image2 is modified by traversing in the right to left direction Afterwards final binary image is obtained by doing an OR operation on the two binary images Bin Image x y Bin Imagel x y OR Bin Image2 x y Combining the Color amp Edge Analysis Results 0071 The motion blobs obtained in the color map BC BC1 and edge map BE BEI are refined using the blob association between the color and edge Based on the association and consistency the unnecessary blobs will be eliminated and
25. h motion detection is a part ofa more sophisticated process such as object tracking or identifica tion and video compression 0007 It is therefore desirable that video signal motion detection be as accurate as is technically practical Nov 2 2006 BRIEF DESCRIPTION OF THE FIGURES 0008 FIG 1 is a flowchart illustrating learning a back ground image for video motion detection consistent with an example embodiment of the invention 0009 FIG 2 is a flowchart illustrating a video motion detection algorithm consistent with an example embodiment of the invention 0010 FIG 3 is a flowchart illustrating generation of an edge strength image consistent with an example embodi ment of the invention 0011 FIG 4 is a flowchart illustrating combination of edge strength image data and binary image data consistent with an example embodiment of the invention 0012 FIG 5 is a flowchart illustrating a method of updating a background image consistent with an example embodiment of the invention 0013 FIG 6 is a flowchart illustrating combination of color and edge information to estimate motion in a video stream consistent with an example embodiment of the invention 0014 FIG 7 is a flowchart illustrating finding an edge of a moving object in a video stream consistent with an example embodiment of the invention 0015 FIG 8 is a flowchart illustrating application of a color luminance motion detection algorithm to v
26. ideo motion detection consistent with an example embodiment of the invention DETAILED DESCRIPTION 0016 In the following detailed description of example embodiments of the invention reference is made to specific examples by way of drawings and illustrations These examples are described in sufficient detail to enable those skilled in the art to practice the invention and serve to illustrate how the invention may be applied to various purposes or embodiments Other embodiments of the inven tion exist and are within the scope of the invention and logical mechanical electrical and other changes may be made without departing from the subject or scope of the present invention Features or limitations of various embodi ments of the invention described herein however essential to the example embodiments in which they are incorporated do not limit the invention as a whole and any reference to the invention its elements operation and application do not limit the invention as a whole but serve only to define these example embodiments The following detailed description does not therefore limit the scope of the invention which is defined only by the appended claims 0017 In one example embodiment of the invention a moving object is detected in a video data stream by extract ing color information to estimate regions of motion in two or more sequential video frames extracting edge informa tion to estimate object shape of the movin
27. ield cases in indoor and far field cases in outdoor could cause split motion blobs resulting in multiple track IDs for the same object followed by erroneous classification due to lack of shape information On the other hand any object moving at very high speed may not be available in the frame ROI for sufficiently long duration to be assigned a track ID and may pose problems to further processing such as classification The dependency can also be viewed from another perspec tive the frame rate perspective If the video frame capture rate is very low less than 5 fps even slow moving objects will tend to stay for a very short duration within the scene while very high capture rate greater than 20 fps would result in slow moving objects being learnt as BGND hence would go undetected It is therefore suggested to use a capture rate of 5 to 15 fps for best results Nov 2 2006 Minimum Object Size MOS 0077 The MOS specified as the count of FGND pixels for a given moving object is in some embodiments among the most critical factors to ensure best performance The MOS is one of the primary aspects of any scene and any object The MOS setting assumes bigger proportions due to the fact that all pixels on the body of the object need not necessarily show perceivable motion information This would lead to the fact that on an average 75 to 90 of the object pixels only get represented in the motion segmented result Coupled to this far fi
28. l binary image is obtained by doing an OR operation on the two binary images Bin img Bin imgl OR Bin img2 This method of combining the edge strength image data and binary image data is illustrated in FIG 4 Background Update 0034 There is a need to update the learned background scene as one cannot be sure of some image characteristics such as the same level of illumination over an extended period of time Also an object that was stationary during the learning period may start moving at a later time or a new US 2006 0245618 Al object may enter the camera field of view and remain stationary for a long period Under such circumstances it is desired to update the learnt background scene to have effective motion detection The procedure adapted for updat ing the background is given below 0035 Similar to the initial learning of background the current image fn and the image which is five frames old fn 5 are used to obtain Diff_img and Sum_img Equations 1 amp 2 Ifa given pixel in the Diff_img satisfies the following inequality condition then the previous background image at that location is replaced by the weighted sum of present image and the previous background image If Diff_img p q lt kl Sum img p q Bg_img p q a fn p q 1 a Bg_img p g 7 a Learning rate for the background pixels The value of a can be varied between zero and one depending on the required learning rate kl Constant
29. mera is converted into a grayscale image and the resulting gray level image is passed through an averaging filter such as a 3x3 neighborhood averaging filter to reduce the effect of noise This filtered image is referred to as current image in the subsequent discussions The second step involves learning the static background scene and for this purpose the current image and the image which was captured five frames earlier are used The algorithm is designed to pick up only static background pixels and reject those pixels which correspond to moving objects in the foreground In the third step this learned background image along with the current image are utilized to generate a division image In the fourth step the division image is subjected to a threshold operation to get a segmented binary image wherein all the background pixels are set to zero and the moving foreground pixels are set to 255 The fifth step involves generating edge strength image for both division image and the current image The sixth step involves finding the correspondence between the binary image and the edge strength image The output from this step is subjected to median filtering in the seventh step to get final segmented binary image output The eighth step involves subsequent updating the background pixels using the current image and the image that was captured five frames earlier Further details of individual steps in one specific example embodiment are given below
30. mp edge models respectively The models basically learn the background information in the frames These models are then threshold ed using standard deviation information to conclude whether a pixel belongs to the foreground FGND or background BGND leading to the formation of motion confidence map The algorithm flow for the color or Luminance and edge based analysis is described in the flow diagram shown below The method starts with the computation of the mean and difference images for the current frame at each pixel as given by the equations DEN 11 NY Oe Ya y avg Ha y 12 NOY OY HUY 13 Nov 2 2006 Where 0039 n nth frame 0040 Y y Luminance 0041 G y Green pixel 0042 1 y pixel mean at position x y 0043 AC mean difference Image 0044 R amp y Red pixel 0045 B x y Blue pixel 0046 o Learning parameter Adaptive threshold computed using the current frame and previous frame difference and the mean of the difference as given below 14 a 212 as D You DI I Yat 3 0 cf I Where 0047 The average alpha over the frames is used for background model update r rows c columns Tayo Ayyy PAY2 15 avg avg 0048 The value of Alpha is normalized based on the count of the motion pixels only The variation of thus computed Alpha is shown in the plot shown above and varies most appropriately according to the extent of the motion in the frame Whene
31. multiplying factor as chosen in the earlier background learning routine Equation 1 This updated Bg_img is used in the next frame to obtain the Div_img in the VMD routine and the whole process repeats This method is shown in flowchart form in FIG 5 0036 The method described above is an example embodiment ofthe present invention illustrating how extrac tion of various information from a video stream can be used to effectively detect motion for applications such as security monitoring and object identification A Second Algorithm Example 0037 In another example color and edge information are extracted from the video frame sequence to estimate motion ofan object in a video stream The color information is used as the first level cue to extract motion regions These motion regions blobs usually do not account for the full shape amp contour of the moving object The incomplete blobs thus obtained from the color model are boosted by second level processing using the edge information The final motion segmented result is then obtained as the collated information of the color and edge foreground confidence maps 0038 This second video motion detection algorithm involves the generation of the mean and variance images computed pixel wise based on the color amp edge informa tion of each of the frames in the video data These mean and variance images are then updated dynamically using the method of moments to help build the color a
32. nitoring system of claim 7 wherein information is extracted to estimate motion in only a selected region of interest in the video data stream 13 A machine readable medium with instructions stored thereon the instructions when executed operable to cause a computerized system to extract color information to estimate regions of motion in two or more sequential video frames extract edge information to estimate object shape of the moving object in two or more sequential video frames and combine the color information and edge information to estimate motion of the object 14 The machine readable medium of claim 13 the instructions when executed further operable to cause the computerized system to extract contrast information from two or more sequential video frames and combining the extracted contrast information with the color information and edge information in estimating motion of the object 15 The machine readable medium of claim 13 wherein combining the color information and edge information com prises correlating the information to estimate the position and motion of the object 16 The machine readable medium of claim 13 the instructions when executed further operable to cause the computerized system to update a learned background image record using the color information and edge information 17 The machine readable medium of claim 13 wherein the video stream comprises video frames at a frame rate between and including
33. or motion detection the current image is typically subtracted from the background image and the background subtracted image is evaluated using a threshold to extract all the moving foreground pixels In some embodiments of the present invetntion we normalize the current image by dividing it with the sum of current image and the back ground image and the resulting division image Div img is used for extracting the moving foreground pixels from the static background pixels Div_img fn Bg_img fn 4 0027 To segment this division image into background and moving foreground pixels target pixel it is desired to subject the image to a thresholding operation It is evident from the above equation Equation No 4 that all those pixels in the current image fn which are equal to the corresponding pixels in the background image Bg img would yield a value of 0 5 in the Div img whereas all target US 2006 0245618 Al pixels show up as deviations on either side of this mean value 0 5 However it is advisable to find this mean value from the image itself as there could be variations in light levels from frame to frame Hence the mean gray level of the division image Div_img was first determined While finding the mean those pixels that are in the neighborhood of 0 5 0 4 to 0 6 range were only considered After getting the mean gray level value of the division image it is multiplied by two different constants k2 and k3 to generate lo
34. s are obtained as follows Difference image Dif_img abs fn fr 5 1 Sum image Sum_img f7 fn 5 2 Threshold img k1 Sum img 3 k1 Constant multiplying factor which decides the gray level variation between the two video frames that can be allowed to qualify a given pixel as a background pixel or not It is chosen in the range of 0 0001 to 0 001 0023 The value of each and every pixel in the Dif img is compared with a corresponding pixel in the Thresh old img and if a given pixel is less than the Threshold img value it is considered as static background pixel If Dif img p q Threshold img p q Bg img p q fn p q 0024 Where Bg img p q is the learnt background image pixel p indicates row and q indicates column number 0025 The location row p amp column q of all the pixels which do not satisfy the above condition is stored in a sequential array In the next frame only those pixels which are available in the sequential array are tested for the above If condition and the process is repeated in every frame till the number of learnt background pixels is same as the image size Then it declares that the background is learnt This learnt background image is use in the subsequent Video Motion Detection algorithm FIG 1 shows a flowchart of one example method of learning a background image con sistent with the example embodiment of the invention described above Video Motion Detection 0026 F
35. s chosen as 0 9 0065 Above analysis until the step 17a is used during the initial background learning phase of the algorithm and if the number of learned background pixels is same or comparable to the image size the algorithm sets the flag indicating completion of learning process Further to this the same steps until the step 17a along with the step 175 together perform moving object segmentation The procedure adapted for updating the background is described below 0066 Similar to the initial learning of background the current image f and the image which is five frames old fu s are used to obtain Diff Image and Sum Image Equations 14 amp 15 If a given pixel in the Diff Image satisfies the following inequality condition then the previ ous background image at that location is replaced by the weighted sum of present image and the previous background image US 2006 0245618 Al If Diff Image x y lt kl Sum Image x y Bond Image x y a Bgnd Images y 1 a fa x y 28 a Learning rate Value of o can be varied between zero amp one depending on required learning rate Where Constant k1 Multiplying factor as chosen in the earlier background learning routine Eqn 14 This updated Bgnd Image is used in the next frame to obtain the Div Image in the VMD routine and the whole process repeats Edge Strength Model 0067 The procedure involves computing the row differ ence and column di
36. the final output is obtained by OR of all the maps as given below Final Binary Map B BC BC1 BE BE1 Summary of the Second Example Video Motion Detection Algorithm 0072 The second example video motion detection algo rithm presented here results in near 100 accuracy for most datasets except low illuminated scenes in detecting a moving object The algorithm extracts complete shape ofthe US 2006 0245618 Al moving objects and has nearly identical performance for slow or fast moving objects large or small objects indoor or outdoor environments and far field or near field objects 0073 Performance also remains stable for relatively low minimum object sizes on the order of 16 pixels in an outdoor far field environment and 150 pixels in an indoor near field environment Performance is also stable across video frame capture rates varying from 5 to 15 fps with low false motion detection on the order of one or two motions per camera per hour in a typical environment or two to three motions per camera per hour in an environment with a relatively large amount of background change 0074 Environmental factors such as thick shadows low illumination or cloud movement low to moderate wind causing tree motion low to moderate rainfall and low to moderate snowfall are all manageable using the example embodiments presented here Performance remains depen dent in part on factors such as separation between moving objects distinction
37. ver fast moving objects slow moving objects are encountered alpha increases or decreases respectively for the most optimal update of the BGND Background Learning Mechanism 0049 The background learning which forms the back bone of the second example algorithm is based on a hier archical fusion of a color and b edge models obtained corresponding to the pixel state using its RGB color amp Edge information as shown in the flowchart of FIG 6 Edge Model 0050 The color model does not give the smooth edge To get the fine edge of the object to improve the result edge model is applied to Y channel as given below An edge sharpening filter is first applied on the Y channel image data Y EdgeFilter EF X 0051 Output X obtained after passing through the high pass filter is fed to Sobel filter to get the horizontal and vertical edges The mean and the zero mean are computed for the each channel as Isa 5 Edge HY H1 rage epes 5 16 Usviny 5X FE age Bue AIST Grape Hsv ay Y 17 Where 0052 S x y Sobel Horizontal edge data 0053 S x y Sobel vertical edge data US 2006 0245618 Al 0054 Wsrm y Sobel Horizontal mean 0055 Usyay y Sobel Vertical mean 0056 c4 Constant 0057 The mean and delta gradient images are computed for the horizontal and vertical Sobel image as below Mean gradient Al Usa 53 Say 5 18 NIY S vay GP 19 Delta Gradient A12 A1 A2 20 A A1 A2 A12 21
38. wer and upper threshold as indicated below High threshold k2 mean_Div_img 5 Low_threshold k3 mean_Div_img 6 0028 In our implementation the value of k2 and k3 are chosen as 1 1 and 0 9 respectively assuming a 10 spread around the mean for background pixels This assumption proved to be a valid one when tested on a variety of video data sets Alternatively the values of k2 and k3 can be chosen by computing the standard deviation of those pixel gray levels that are used for finding the mean value The lower threshold operates on those object pixels that are darker than the background and the higher threshold oper ates on the object pixels that are brighter than the back ground 0029 Segmentation of image into background and target regions is done by comparing each and every pixel with high and low thresholds as per the logic given below If Div_img p q lt Low threshold OR Div_img p q gt High threshold Bin img p q 255 Else Bin img p q 0 0030 Bin img is the segmented binary image wherein all pixels indicating 255 correspond to moving foreground pixels and pixels with zero values correspond to background region The flowchart of the VMD algorithm is given in FIG 2 Generation of Edge Strength Image 0031 If an object that is learned as background earlier starts moving then it shows up as two objects one at the new location and one at the location where it was residing earlier This happens because it
Download Pdf Manuals
Related Search