In video coding, motion compensation techniques have been successfully applied to reduction of temporal redundancies. For motion estimation, the block matching algorithm (BMA) is currently preferred approach due to its simplicity and robustness. Despite its widespread use, the BMA possesses several drawbacks such as enormous amount of computation, difficulty of sub-pixel motion estimation and unreliable motion fields in sense of the true motion.
On the other hand, the block recursive algorithm (BRA) is an efficient method for solving the problems of the BMA. The BRA is based on the gradient method. In the gradient method, assuming that the luminance intensity changes between successive frames are caused by the translation of an object, motion vectors are iteratively estimated along the luminance gradient direction. For videos with slow motions, it has been known that the BRA is quite good performance and very high convergence speed. Moreover, it is very convenient to estimate a motion vector field with a sub-pixel precision. However, it has been reported that the BRA is not stable and reliable especially when there are complicated and large motion.
In this thesis, in order to overcome the drawbacks of the BRA, block segmentation-based motion estimation techniques are investigated.
First, a new motion estimation method based on an irregular block subdivision is proposed. In the proposed method, an image block in boundary of moving object is split into four smaller subblocks of various sizes horizontally and vertically, according to the boundary position. This method is an efficient method for motion estimation of blocks including horizontal or vertical boundary.
Second, a bi-sectional block motion estimation method with straight boundary approximation is proposed. The proposed method allows various segmentation patterns. And, by the approximated line of object boundary in the block, a block is subdivided into two segments, and motion vectors are seperately estimated for each segment. Experimental results show that two proposed methods can achieve better prediction gain and improved subjective quality in object boundary regions in spite of additional overhead information for segmentation pattern.
For large motion estimation, a constraint line grouping method is proposed. It is based on the investigations for large motion block that the magnitude of estimated motion is increased by removing spatial gradients irrelevant to the actual motion, and spatial gradients obtained from the current image can give better results than those by the reference image. The proposed method is applied to every iteration for vector updating according to the characteristics of spatial and temporal gradients. Experimental results show that reliable motion vectors are obtained by the proposed method in case of large motion block compare with the conventional BRA.
When the above method is combined with the bi-sectional segmentation method, an additional prediction gain is achieved. And the combined scheme is applied to video coding with some modification of MPEG-1. It is shown that the combined scheme can give higher overall coding performance than the BMA.