Efficient coders for large tree-structured dictionaries of tilings

Algorithms for best basis search in tree-structured dictionaries have been effectively used for many problems. An important class of best basis algorithms are methods that search for an optimum rectangular tiling for a block. These methods have proven to be promising in image and video compression, due to their ability to adapt to the geometry of motion in video coding applications and to the geometry of image textures and shapes in still picture coding. A major impediment to their practical use is the need to encode the tiling chosen by the encoder. If this is not done carefully, the resulting overhead bits may completely negate the advantages offered by the adaptivity of the tiling. In this paper, we devise efficient entropy coders for two large dictionaries. We show that our algorithms result in very significant savings compared to naive fixed-length encoding methods, and illustrate them using a video coding application.