Visual Motion Extraction Based On Block Matching And Optical Flow Field

With the development of computer, communication and the amount of videodata is enlarged at a explosive speed multimedia technologies, how to orgnize,manage,express and retrieve these video data efficiently becomes a hot issue onvideo retrieval. This leads to the emergence of content-based video retrievaltechnology. Motion analysis in video images is a hot topic among many sciencedomain including Computer,Science,Computer Vision and Artificial Inteligence.By extending the analysis from single, static image to moving images, motionanalysis can obtain more useful information than static image, like the feature ofthe motion and the moving objects recognition. As the key technique of computervision and digital video processing, motion estimation of sequence images showsmore and more important position and role not to be ignored in the variousdirections of production and life in society and has wide application value inindustry,commerce,country defense,,medicine,Internet technology, etc. Withgreat application sofwireless communication, there are great challenges in thecoding and transmission technology of video. Because data quantity of video isvery big, fast coding algorithm used must have high data compression ratio andlow complexity, and least data quantiy used can transmit most information quantityin order to satisfy video's real time request, when video is transmitted in narrowwireless channel. Motion Estimation is one of key technology in the video imagecompression coding, that is the important part of this thesis.As a result, video sequence has rather relativity on time axis, MotionEstimation and Motion Compensate can reduce this relativity efectively, so it hasbeen widely used in many video standards such as MPEG, as a key module invideo encoder, motion estimation is rather complex in computation. For this reason,fast motion estimation has always been a favorite to the researchers in the field. Video images equences generally are obtained through video camera in thespace monitoring. Usually the camera is fixed on a plate form scanning over therelevant space area for catching moving target. So the background will have aglobal motion which will bring badly difficulty for the detection of the movingtargets. And considering the data compression, layering of video images based oncontents, etc…, the global motion estimation and compensation are required.This thesis includes two important parts of representative Motion EstimationAlgorithm: Motion Object Detect Algorithm Based on Block Match and MotionObject Detect Algorithm Based on Optical flow. We use Block Match obtion theglobal motion and Optical flow obtion the local motion.1.Motion Object Detect Algorithm Based on Block MatchBlock matching technique has been widely used in video compression. At thebeginning, a fully survey about motion estimation algorithms is given Matchingalgorithm based on block becomes to be considered, owing to its simplistic method,good estimation eficiency and potential to be implemented for the real-timeapplication using the available hardware. On the base of understanding for blockmatching problem in nature, a systematic summarize is made for all current blockmatching algorithm in the world. From the diferent search algorithm and searchcriteria adopted by full search method , two-dimension logarithmic searchalgorithm, three step search, based on block, and diamond search algorithm, etc, wehave analysed their applicability and compared them in terms of computationalcomplexity.A lot of algorithms have been proposed to accelerate the estimation speed,among those algorithms, block sum pyramid algorithm (BSPA) is widely used. Inthis thesis, a new block sum pyramid algorithm (NBPSA) to motion estimation ispresented. Compared with BSPA, NBSPA estimate the vector of the minimummean absolute difference (MADmin). In the mean time, instead of the valueupdated level by level, the estimation of MAD is updated row by row from top tobottom. Experimental results showed that compared with exhaustive searchapproach in BSPA, NBSPA algorithm can be used to arrive at the same result withmuch less computational complexity.(1) Reliable prediction of initial search pointThere exist high correlations between motion vectors those in temporally andspatially adjacent blocks, and that can be seen from the vectors' value anddirection, which implies that a block's motion vector can be predicted with itsadjacent blocks' motion vectors. We can choose a predictor that reflects the currentblock motion trend as the initial search position, instead of the (0,0) position, thepredictor is more close to the global minimum position, and that improves theperformance of the center based block matching algorithm both in terms of speedup and veracity. In this thesis, we define the (0,0) motion vector (MV0), the motionvectors of the blocks on the left (MV1), top (MV2), and top-right (MV3), and themotion vector of the collocated block in the previous frame at time t-1 (MVt-1) asCandidate Set A. In the first step of the search process, the best candidate isselected as the predictor from set A, and then the predictor is taken as the center ofthe search to carry on the following search steps.(2) Renew the lower limit graduallyFor the other block, from the top down, from the first row to the last row. Wecompute every numerical value that we can compute and compare to the presentMADmin. If the current number is bigger than the MADmin, we can think thisblock is not the best block. We can stop computing and start to compute the nextblock;Or else start to compute next block.2.Motion Object Detect Algorithm Based on Optical flowFor the other block,from the top down,from the first row to the last row, wecomputer the MADmin. Optical Flow Field Estimation Algorithms, one importantkind of picture motion estimation as the essential task of video processing, inmotion content-based video retrieval, users are more concerned with the localobject motion than the global camera motion. Optical Flow are typically based onthe basic constraint Equation of Optical Flow Estimation , sponsored by Horn andSchunk , which is in fact not complete due to the lack of enough constraints.Categories of Optical Flow Estimation Algorithms, falling into the two categoriesof Global Optimizing Algorithms and Local Optimizing Algorithms, have beensponsored and in this thesis they are compared and a typical up to date instance ofthem analyzed so that the track of the optimization developing is thus recovered.Considering the traditional optical flow algorithm couldn't detect the movingobjects in case the displacements between two continuous frames were less thanone pixel, we developed an improved gradient-based optical flow algorithm thatseparates continuous frames into two groups. The optical flow fields of the middleframe were computed respectively. The process of gradient computing used3D-Sobel operator. A parameter was defined to determine the final optical flowfield of the middle frame. The results show that the algorithm can accurately andvalidly detect different object s with different velocities in static back-ground.