Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire de communications audiovisuelles LCAV)

Rate-distortion optimized geometrical image processing

Shukla, Rahul ; Vetterli, Martin (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2004 ; no 2992.

Ajouter à la liste personnelle
    Summary
    Since geometrical features, like edges, represent one of the most important perceptual information in an image, efficient exploitation of such geometrical information is a key ingredient of many image processing tasks, including compression, denoising and feature extraction. Therefore, the challenge for the image processing community is to design efficient geometrical schemes which can capture the intrinsic geometrical structure of natural images. This thesis focuses on developing computationally efficient tree based algorithms for attaining the optimal rate-distortion (R-D) behavior for certain simple classes of geometrical images, such as piecewise polynomial images with polynomial boundaries. A good approximation of this class allows to develop good approximation and compression schemes for images with strong geometrical features, and as experimental results show, also for real life images. We first investigate both the one dimensional (1-D) and two dimensional (2-D) piecewise polynomials signals. For the 1-D case, our scheme is based on binary tree segmentation of the signal. This scheme approximates the signal segments using polynomial models and utilizes an R-D optimal bit allocation strategy among the different signal segments. The scheme further encodes similar neighbors jointly and is called prune-join algorithm. This allows to achieve the correct exponentially decaying R-D behavior, D(R) ~ 2-cR, thus improving over classical wavelet schemes. We also show that the computational complexity of the scheme is of O(N logN). We then extend this scheme to the 2-D case using a quadtree, which also achieves an exponentially decaying R-D behavior, for the piecewise polynomial image model, with a low computational cost of O(N logN). Again, the key is an R-D optimized prune and join strategy. We further analyze the R-D performance of the proposed tree algorithms for piecewise smooth signals. We show that the proposed algorithms achieve the oracle like polynomially decaying asymptotic R-D behavior for both the 1-D and 2-D scenarios. Theoretical as well as numerical results show that the proposed schemes outperform wavelet based coders in the 2-D case. We then consider two interesting image processing problems, namely denoising and stereo image compression, in the framework of the tree structured segmentation. For the denoising problem, we present a tree based algorithm which performs denoising by compressing the noisy image and achieves improved visual quality by capturing geometrical features, like edges, of images more precisely compared to wavelet based schemes. We then develop a novel rate-distortion optimized disparity based coding scheme for stereo images. The main novelty of the proposed algorithm is that it performs the joint coding of disparity information and the residual image to achieve better R-D performance in comparison to standard block based stereo image coder.
    Résumé
    Puisque les éléments géométriques, comme les bords, représentent des informations perceptuelles parmi les plus importantes dans une image, l'exploitation efficace de telles informations géométriques dans les images est un ingrédient principal de nombreuses applications du traitement d'image, y compris la compression, la réduction du bruit et l'extraction de caractéristiques. Par conséquent, le défi pour la communauté du traitement d'image consiste à concevoir des méthodes géométriques efficaces capables de discerner la structure géométrique intrinséque des images naturelles. Cette thèse se concentre sur le développement d'algorithmes efficaces basés sur des arbres pour atteindre le comportement optimal de la fonction rate-distortion (R-D) pour certaines classes simples d'images géométriques telles que les images polynômiales par morceaux avec des frontières polynômiales. Une bonne approximation de cette classe permet de développer des méthodes d'approximation et de compression efficaces pour des images avec de fortes caractéristiques géométriques et également, comme les résultats expérimentaux le montrent, pour des images naturelles. Nous étudions d'abord les signaux polynômiaux par morceaux aussi bien dans une dimension (1-D) que dans deux dimensions (2-D). Pour le cas 1-D, notre méthode est basée sur la segmentation du signal par arbre binaire. Cette méthode fait une approximation des segments du signal en utilisant des modèles polynomiaux ainsi qu'une stratégie d'attribution des bits aux différents segments du signal qui est optimale au sens de R-D. En outre, cette méthode code des voisins similaires conjointement et est appelée algorithme tailler-joindre "prune-join". Ceci nous permet d'obtenir le comportement de décroissance exponentielle correct au sens de R-D, D(R) ~ 2-cR, et de ce fait de surpasser les méthodes classiques par ondelettes. Nous prouvons également que la complexité de la méthode est de O (N logN). Nous généralisons ensuite cette méthode pour le cas 2-D en utilisant un "quadtree", ce qui conduit aussi à une décroissance exponentielle de la fonction R-D pour des images polynômiales par morceaux, avec une complexité faible de O (N logN). Là encore, la solution consiste en une stratégie de joindre et tailler optimisée au sens de R-D. De plus nous analysons l'efficacité R-D des algorithmes par arbres proposés pour des signaux régulier par morceaux. Nous montrons que les algorithmes proposés permettent d'obtenir le comportement asymptotique R-D de décroissance polynômiale, comme celui en présence d'un oracle, aussi bien pour le scénario à une dimension que pour celui à deux dimensions. Des résultats théoriques ainsi que numériques montrent que les méthodes proposées surpassent les codeurs par ondelettes pour le cas 2-D. Nous considérons ensuite deux problèmes intéressants de traitement d'image, à savoir la réduction du bruit et la compression d'images stéréo, dans le cadre de la segmentation par structures d'arbre. Pour le problème de la réduction du bruit, nous présentons un algorithme par arbre qui effectue la réduction du bruit en comprimant l'image bruitée et permet d'obtenir une qualité visuelle améliorée en discernant des éléments géométriques, comme les bords, dans les images avec plus de précision que les méthodes par ondelettes. Nous développons ensuite une méthode de codage innovatrice basée sur la disparité et optimisée au sens de R-D. La nouveauté principale de l'algorithme proposé consiste dans le fait qu'il effectue le codage de l'information de disparité et de l'image résiduelle conjointement pour atteindre une efficacité R-D supérieure par rapport aux codeurs classiques d'images stéréo par blocs.