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.