Quad-Tree Motion Modeling With Leaf Merging

In this paper, we are concerned with the modeling of motion between frames of a video sequence. Typically, it is not possible to represent the motion between frames by a single model and therefore a quad-tree structure is often employed where smaller, variable size regions or blocks are allowed to take on separate motion models. Previous work into quad-tree representations has demonstrated the sub-optimal performance of quad-trees where the dependency between neighboring leaf nodes with different parents is not exploited. Leaf merging has been proposed to rectify this performance loss as it allows joint coding and optimization of related nodes. In this paper, we describe how the merging step can be incorporated into quad-tree motion representations for a range of motion modeling contexts. In particular, we study the impact of rate-distortion optimized merging for two motion coding schemes, these being spatially predictive coding, as used in H.264, and hierarchical coding. We present experimental results which demonstrate that node merging can provide significant gains for both the hierarchical and spatial prediction schemes. Interestingly, experimental results also show that in the presence of merging, the rate-distortion performance of hierarchical coding is comparable to that of spatial prediction. We pursue the case of hierarchical coding further in this paper, introducing polynomial motion models to the quad-tree representation and exploring resolution scalability of the merged quad-tree structure. We also present a theoretical study of the impact of leaf merging in modeling motion, identifying the inherent advantages of merging which give rise to a more efficient description of frame motion.

I. Introduction

For modeling image features, the quad-tree structure is often used as it allows an image to be recursively divided into smaller regions with each region represented by a suitable model. For image compression, which can be considered a form of image modeling, the quad-tree representation is attractive as it lends itself to direct rate-distortion optimization, allowing a Lagrangian cost function to be globally minimized using tree pruning strategies. In this paper, we are concerned with the modeling of motion between frames of a video sequence. Typically, it is not possible to represent the motion between frames by a single model and therefore a quad-tree structure is employed where smaller, variable size regions or blocks are allowed to take on separate motion models.