#! /Library/Frameworks/Python.framework/Versions/Current/bin/python """ Name: Shawn Lankton Project Number: 1 Algorithms Used: The algorithm operates as follows: 1) A change map is computed using a recursive average of frame-to-frame difference images. This is weighted by the "forget rate" parameter. The higher the "forget rate" the quicker old differences are forgotten 2) This difference map is thresholded to produce a mask of pixels that have been relatively stable. This is controled by parameter "var_thresh" 3) "Stable" pixels are then incorporated into the background model by a recursive average. Their incorporation speed is goverened by "learning rate". The higher this parameter, the faster new information is incorporated. 4) The distance between the current image and the background model is taken. This becomes the motion field. 5) The motion field is smoothed with a median filter with size = "smooth_size" and thresholded by "motion thresh". This produces a binary output of pixels that have salient motion 6) A history of the previous 9 binary motion results is collected. This is summed each iteration to compute the ADF. Insights: 1) Learning should happen realtively quickly to account for drastic changes in lighting, camera position, etc. These changes happen over 1 or 2 frames, but remain for scores of frames. With slow background learning rates, big errors can accumulate. 2) The background model should not be updated with statistics from moving pixels. By excluding moving pixels from the background, the correct background can be captured much more quickly. 3) Smoothing the motion field helps eliminate small bits of noise due to aliasing on edges withing the image and fine-scale texture variations (like trees, and grass). 4) If one knew in advance what level of detail they wanted the smoothing could be adjusted accordingly. I have an intermediate size that is a bit too small for cars and a bit too big for people. It works pretty well for detecting both at the same time, though. Issues & Solutions: 1) I had a lot of issues at first with programming in Python. It seems that if I used it like C (with for loops everywhere) thing were incredibly slow. The behavior of "lists" was not intuitive to me. So, I searched out the numpy package which gives a Matlab-esque flavor. This allowed me to move forward quickly. 2) I needed to do gaussian smoothing to keep the final solutions clean. I really didn't want to code these argous details. However, I found that these were implemented in the nd_image module. I used that at first, but it turns out this was depricated, so I figured out how to do it with numpy only. 3) Also, I had some trouble getting packages installed at first (on my mac). I found a website with lots of great packages pre-arranged for macs: http://pythonmac.org/packages/py25-fat/index.html This might be a good one to suggest to mac users in other classes Interesting Facts: 1) A quarter has 119 grooves around the edge. 2) A dime has 118 ridges around the edge. 3) A blue whale's heart is the size of a Volkswagen Beetle. Question: "What would be involved in scaling your program up to larger sequences and larger windows sizes w?" Answer: In my implementation, this would simply be a matter of increasing the queue used to calculate the ADF. If the frame rate was much slower, it would be a good idea to turn down the "learning_rate" parameter so that slow motion would not be recognized as static background. References: The main algorithmic work is all from my own imagination (although I'd imagine that someone has tried something like this before... Its not earth-shaking-ly novel) I made use of various websites that give examples of how to use Python and modules. http://www.pythonware.com/library/pil/handbook/image.htm http://www.scipy.org/Documentation http://www.scipy.org/Numpy_Example_List_With_Doc http://www.scipy.org/NumPy_for_Matlab_Users http://structure.usc.edu/numarray/module-numarray.ndimage.html http://cours-info.iut-bm.univ-fcomte.fr/docs/python/numarray/numarray.nd_image.filters-module.html """ from FrameWork import * from numpy import * import ImageFilter import numpy import Image # import numarray.nd_image # black, purple, blue, green, green-yellow, yellow, orange, red, white Colors = array([[0,0,0], [128,0,128], [0,0,255], [0,128,0], [173,255,47], [255,255,0], [255,165,0], [255,0,0], [255,255,255]]) learn_rate = 1 forget_rate = 1 var_thresh = 50 motion_thresh = 50#75 smooth_size = 7 def Main(SeqName='20061129-01', start=1850, end=1859) : MyTrial = Trial(Update=False) sin = Seq(MyTrial, SeqName) sout = Seq(MyTrial, 'ADF') # interesting intermediate outputs smodel = Seq(MyTrial,'DEBUG_bgmodel') ssmotion = Seq(MyTrial,'DEBUG_smooth_motion') sbmotion = Seq(MyTrial,'DEBUG_binary_motion') sz = sin.Load_Frame(start).size img = numpy.asarray(sin.Load_Frame(start)).astype('float32') model = img.copy(); # data model mu = img.copy(); # data average dvar = ones((sz[1],sz[0])) # data variance dist = zeros((sz[1],sz[0])) # data variance history = zeros([sz[1],sz[0],8]) for fn in range(start, end+1) : print 'on %(current)d of %(total)d.' %{"current": fn-start, "total": end-start} #get current and previous frame pre = img img = numpy.asarray(sin.Load_Frame(fn)).astype('float32') #compute average frame-to-frame difference (recursive average) dist = (dist+sum(abs(img-pre),2))/(forget_rate*2) #get the ones that aren't changing mask=zeros((sz[1],sz[0])) mask[dist0]=(model[maskrgb>0]+learn_rate*img[maskrgb>0])/(1+learn_rate) ############## DEBUG OUTPUT E######################## imodel = Image.fromarray(model.astype('uint8')) smodel.Store_Frame(fn, imodel) ###################################################### #subtract background and smooth to get motion field motion=sum(abs(model-img),2) motion=motion/(motion.max())*255 motion=smoothPIL(motion,smooth_size) ############## DEBUG OUTPUT E######################## smotion = motion.copy() smotion = smotion/smotion.max()*255 smotion = Image.fromarray(smotion.astype('uint8')) ssmotion.Store_Frame(fn, smotion) ###################################################### #threshold and morphology to get binary motion mask motion[motionmotion_thresh]=1; ############## DEBUG OUTPUT E######################## bmotion = motion.copy() bmotion = bmotion*255 bmotion = Image.fromarray(bmotion.astype('uint8')) sbmotion.Store_Frame(fn, bmotion) ###################################################### #update queue of previous motion masks and compute ADF history[:,:,7]=history[:,:,6] history[:,:,6]=history[:,:,5] history[:,:,5]=history[:,:,4] history[:,:,4]=history[:,:,3] history[:,:,3]=history[:,:,2] history[:,:,2]=history[:,:,1] history[:,:,1]=history[:,:,0] history[:,:,0]=motion ADF = sum(history,2) ADFc = adf2adfc(ADF) #colorize the 0-8 version ############## FINAL OUTPUT E######################## result = Image.fromarray(ADFc.astype('uint8')) sout.Store_Frame(fn, result) ###################################################### MyTrial.Done() # colorizes the adf def adf2adfc(adf): sz = adf.shape adfc = zeros((sz[0],sz[1],3)) for i in range(9): adfc[adf==i]=array(Colors[i,:]) return adfc # converts a grayscale image to RGB def g2rgb(a): sz = a.shape r = zeros((sz[0],sz[1],3)) r[:,:,0]=a r[:,:,1]=a r[:,:,2]=a return r def smoothPIL(a,smooth_size): # gaussian (kinda) # k = ImageFilter.Kernel((5,5),[0.0318,0.0375,0.0397,0.0375,0.0318,0.0375,0.0443,0.0469,0.0443,0.0375,0.0397,0.0469,0.0495,0.0469,0.0397,0.0375,0.0443,0.0469,0.0443,0.0375,0.0318,0.0375,0.0397,0.0375,0.0318]) # img = Image.fromarray(a.astype('uint8')).filter(k) # built-in "blur" # img = Image.fromarray(a.astype('uint8')).filter(ImageFilter.BLUR) img = Image.fromarray(a.astype('uint8')).filter(ImageFilter.MedianFilter(smooth_size)) return numpy.asarray(img).astype('float32') # these were my calls to make the program run # Main('20060306-01',20,149) # 20-149 #london cars # Main('20061115-02',2741,2890) # 2741-2890 #rainy physics # Main('20061129-01',1850,1860) # 1850-1860 #short physics # Main('20070403-09',130,329) # 130-329 #skiles walkway Main('20060306-01',20,149)