Abstract
This work discusses the usefulness of hierarchical region based representations for image and video processing. Region based representations offer a way to perform a first level of abstraction and reduce the number of elements to process with respect to the classical pixel based representation. In this work the two representations that have demonstrated to be useful for region based processing are reviewed, namely region adjacency graphs and trees, and it is discussed why tree based representations are better suited for our purpose. In fact, trees allow representing the image in a hierarchical way and efficient and complex processing techniques can be applied on it. Two major issues are discussed in this work: how the hierarchical representation may be created from a given image and how the tree may be manipulated or processed. Two tree based representations have been developed: the Max-Tree, and the Binary Partition Tree. The Max-Tree structures in a compact way the connected components that arise from all possible level sets from a gray-level image. It is suitable for the implementation of anti-extensive connected operators, ranging from classical ones (for instance, area filter) to new ones (such as the motion filter developed in this work). The Binary Partition Tree structures the set of regions that are obtained during the execution of a region merging algorithm. Developed to overcome some of the drawbacks imposed by the Max-Tree – in particular the lack of flexibility of the tree creation and the self-duality of the tree representation –, it has demonstrated to be a representation useful for a rather large range of applications, as it is shown in this work. Processing strategies are focused on pruning techniques. Pruning techniques remove some of the branches of the tree based on an analysis algorithm applied on the nodes of the tree. Pruning techniques applied on the Max-Tree lead to anti-extensive operators, whereas self-dual operators are obtained on the Binary Partition Tree, if the tree is created in a self-dual manner. The pruning techniques that have been developed in this work are directed to the following applications: filtering, segmentation and content based image retrieval. The filtering (in the context of connected operators) and segmentation applications are based on the same principle: the nodes of the tree are analyzed according to a fixed criterion, and the decision to remove or preserve a node usually relies on a threshold applied on the former measured criterion. Pruning is then performed according to the previous decision. As a result, the image associated to the pruned tree represents a filtered or segmented version of the original image according to the selected criterion. Some of the criteria that are discussed in this work are based, for instance, on area, motion, marker & propagation or a rate-distortion strategy. The problem of the lack of robustness of classical decision approaches of non-increasing criteria is discussed and solved by means of an optimization strategy based on the Viterbi algorithm. Content based image retrieval is the third application we have focused on in this work. Hierarchical region based representations are particularly well suited for this purpose since they allow to represent the image at different scales of resolution, and thus the regions of the image can be described at different scales of resolution. In this work we focus on an image retrieval system which supports low level queries based on visual descriptors and spatial relationships. For that purpose, region descriptors are attached to the nodes of the tree. Two types of queries are discussed: single region query, in which the query is made up of one region and, multiple region query, in which the query is made up of a set of regions. In the former visual descriptors are used to perform the retrieval whereas visual descriptors and spatial relationships are used in the latter case. Moreover, a relevance feedback approach is presented to avoid the need of manually setting the weights associated to each descriptor. An important aspect that has been taken into account throughout this work is the efficient implementation of the algorithms that have been developed for both creation and processing of the tree. In the case of the tree creation, efficiency has been obtained mainly due to the use of hierarchical queues, whereas in the processing step analysis algorithms based on recursive strategies are used to get efficient algorithms.