Algorithms for compression of image- or video-signals inevitably comprise a form of signal modeling. However, the statistics of natural image- or video-signals are usually non-stationary, and the whole signal can hardly be characterized efficiently by a single model. Hence, pictures and their corresponding sample arrays are usually decomposed into blocks, such that each block is associated with one of a set of simple models and corresponding model parameters.
A very simple scheme for partitioning an image is based on quadtrees, i.e. trees with four branches at each node. By associating quadratic image regions to the nodes of a quadtree like depicted in figure 1, a particular tree structure describes a particular partitioning of the image. Such tree structures for image partitioning are a tool well suited for compression of images, as very simple algorithms exist to minimize a lagrangian cost functional J = R + LD, thus optimizing the tree structure for spent bit rate R and imposed image distortion D.
On the one hand, the simplicity of this structure allows for direct optimization and a compact signaling (e.g., 1 bit per node). On the other hand, it is unable to describe arbitrary partitionings. Fig 1 depicts this shortcoming by the example of approximating a piecewise constant signal (indicated by the color labels) with quadtree based partitioning. It can be observed, that the systematic decomposition of every block into four child blocks does not allow to jointly represent child blocks that belong to two different parent blocks. Also, to approximate any detail, the only option is to create four separate child blocks of which only one may contain the detail, rendering the other sub-partitions unnecessary (compare Figure 1, blocks 1 to 13).
Hence, the quad tree structure itself implies a certain redundancy among parameters associated to neighboring image blocks. By introducing a leaf merging step subsequent to quadtree-based partitioning, those redundancies are shown to be effectively removed. This step allows to merge a leaf block with one of its neighboring leaf blocks, particularly if the neighboring block has a different parent. Taubman and Mathew [1] noted that quadtree-based motion models involve the same kind of redundancies, and they applied the leaf merging concept to quadtree based coding of parameters for motion compensated prediction, i.e. motion vectors.
High Efficiency Video Coding (HEVC) is a recently developed video compression standard which employs quadtree-based partitioning for motion compensated prediction and transform coding. To eliminate the redundancies among motion parameters characterized above, we developed a coding tool using the leaf merging concept and introduced it into HEVC in form of a block merging algorithm [2].
For each particular motion compensated block, it compiles a list of merge candidates among which one is chosen to be used for the current block. The candidates are drawn from neighboring blocks already coded, so as to exploit spatial redundancies. Figure 2 depicts a possible prediction block partitioning in HEVC, with black dots indicating merge candidates P0..P4 for current block X. By copying parameters among blocks in this way, regions of identical motion parameters are created as indicated by the bold line in Fig. 2 (a).
As encoder and decoder both derive the exact same list, the syntax to signal motion parameters with block merging is very slim, consisting for each block only of a flag, indicating whether merging is to be used, and an index to identify the candidate.
Fig. 2 (b) shows a partitioning for an actual video sequence obtained by quadtree-based partitioning and block merging. The partitioning can be observed to decently capture differently moving objects in the scene.
References
- R. De Forni and D. S. Taubman, On the benefits of leaf merging in quad-tree motion models
- P. Helle et al., Block Merging for Quadtree-Based Partitioning in HEVC