Motion estimation and segmentation

Motion estimation is an important part in many video processing applications, such as video compression, object segmentation, and scene analysis. In all video compression applications, motion information is used to reduce temporal redundancy between frames, thus significantly reduce the required bitrate for transmission and storage of compressed video. In addition, in object-based video coding, video object can be automatically identified by its motion against the background.;In the first part of our research, we proposed a block matching algorithm called Fast Walsh Search (FWS) for video motion estimation. FWS employs two new error measures defined in Walsh Hadamard domain, which are partial sum-of-absolute difference (PSAD) and sum-of-absolute difference of DC coefficients (SADDCC). The algorithm first rejects most mismatched candidates using PSAD which is a coarse measure requiring little computation. Because of the energy packing ability of Walsh Hadamard transform (WHT) and the utilization of fast WHT computation algorithm, mismatched candidates are identified and rejected efficiently. Then the proposed algorithm identifies the matched candidate from the remaining candidates using SADDCC which is a more accurate measure and can reuse computation performed for PSAD. Experimental results show that FWS can give good visual quality to most of video scene with a reasonable amount of computation.;Based on the fixed block size FWS algorithm, we further proposed a fast full-pel variable block size motion estimation algorithm called Fast Walsh Search in Variable Block Size (FWS-VBS). As in FWS, FWS-VBS employs the PSAD as the error measure to identify likely mismatches. Mismatches are rejected by thresholding method and the thresholds are determined adaptively to cater for different activity levels in each block. Early termination techniques are employed to further reduce the number of candidates and modes to be searched of each block. FWS-VBS performs equally well to the exhaustive full search algorithm in the reference H.264/AVC encoder and requires only about 10% of the computation time.;In the second part of our research, we developed a real-time video object segmentation algorithm. The motion information is obtained by FWS-VBS to minimize the computation time while maintaining an adequate accuracy. The algorithm makes use of the motion information to identify background motion model and moving objects. In order to preserve spatial and temporal continuity of objects, Markov random field (MRF) is used to model the foreground field. The block-based foreground object mask is obtained by minimizing the energy function of the MRF. The resulting object mask is then post-processed to generate a smooth object mask. Experimental results show that the proposed algorithm can effectively extract moving objects from different kind of sequences, at a speed of less than 100ms per frame for CIF frame size video.;Furthermore, we modified our proposed segmentation algorithm to handle video sequences that are already encoded in the H.264 format. Since the video is compressed, no spatial information is available. Instead, quantized transform coefficients of the residual frame are used to approximate spatial information and improve segmentation result. The computation time of the segmentation process is merely about 16ms per frame for CIF frame size video, allowing the algorithm to be applied in real-time applications such as video surveillance and conferencing.